P4126 [AHOI2009] 最小割

2018-04-02 21:17:26


一看题目就是最小割

但是这道题需要几个神奇的结论

1、残余网络中有剩余流量的边一定不在最小割方案中

2、残余网络中一条边的两个端点(满足1)还能相互到达,则这条边不在最小割方案中

wgl:一条边的两个端点能相互到达,则它们在割后的同一集合中,所以连接它们的边

肯定不在最小割方案中啊!

3、残余网络中一条边(满足1)的两个端点分别和s,t在同一集合中,则这条边在最小割方案中。

wgl:你不割这条边,最小割肯定得改变!

所以dinic之后用tarjan判断连通性即可

#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
#include<algorithm>
#define reg register
using namespace std;
const int N=4005,inf=1e8;
struct edge
{
    int to,from,nxt,dis;
}edge[120005];
int n,m,s,t,num=1,head[N],dep[N],dfn[N];
int low[N],stack[N],top,cnt,ans,belong[N];
bool exist[N];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void add_edge(int from,int to,int dis)
{
    edge[++num].nxt=head[from];
    edge[num].to=to;
    edge[num].from=from;
    edge[num].dis=dis;
    head[from]=num;
}
inline bool bfs()
{
    queue<int>q;
    memset(dep,0,sizeof(dep));
    q.push(s); dep[s]=1;
    while (!q.empty())
    {
        int u=q.front(); q.pop();
        for (reg int i=head[u];i;i=edge[i].nxt)
        {
            int v=edge[i].to,d=edge[i].dis;
            if (!dep[v]&&d)
            {
                dep[v]=dep[u]+1; q.push(v);
            }
        }
    }
    return dep[t];
}
int dfs(int k,int dis)
{
    if (k==t||!dis) return dis; int sum=0;
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to,d=edge[i].dis;
        if (dep[v]==dep[k]+1&&d)
        {
            int temp=dfs(v,min(d,dis));
            if (temp>0)
            {
                edge[i].dis-=temp;
                edge[i^1].dis+=temp;
                sum+=temp; dis-=temp;
                if (!dis) return sum;
            }
        }
    }
    if (!sum) dep[k]=-1;
    return sum;
}
inline int dinic()
{
    while (bfs()) dfs(s,inf);
}
void tarjan(int k)
{
    int temp;
    dfn[k]=low[k]=++cnt;
    stack[++top]=k; exist[k]=1;
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        if (!edge[i].dis) continue;
        int v=edge[i].to;
        if (!dfn[v])
        {
            tarjan(v);
            low[k]=min(low[k],low[v]);
        }
        else if (exist[v])
          low[k]=min(low[k],dfn[v]);
    }
    if (dfn[k]==low[k])
    {
        ++ans;
        do
        {
            temp=stack[top--];
            exist[temp]=0;
            belong[temp]=ans;
        }while (temp!=k);
    }
}
int main()
{
    n=read(),m=read(),s=read(),t=read();
    for (reg int i=1;i<=m;i++)
    {
        int x=read(),y=read(),z=read();
        add_edge(x,y,z);
        add_edge(y,x,0);
    }
    dinic();
    for (reg int i=1;i<=n;i++)
      if (!dfn[i]) tarjan(i);
    for (reg int i=2;i<=num;i+=2)
    {
        int u=edge[i].from,v=edge[i].to;
        if (edge[i].dis)
        {
            printf("0 0\n"); continue;
        }
        if (belong[u]==belong[v]) printf("0 ");
        else printf("1 ");
        if (belong[u]==belong[s]&&belong[v]==belong[t])
          printf("1\n"); else printf("0\n");
    }
    return 0;
}