[BZOJ1797][AHOI2009]最小割Mincut

bzoj

luogu

sol

一条边出现在最小割集中的必要条件和充分条件。

先跑出任意一个最小割，然后在残余网络上跑出\(scc\)。

一条边\((u,v)\)在最小割集中的必要条件：\(bel[u]!=bel[v]\)

一条边\((u,v)\)在最小割集中的充分条件：\(bel[u]=bel[S],bel[v]=bel[T]\)

code

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

int gi()

{

    int x=0,w=1;char ch=getchar();

    while ((ch<'0'||ch>'9')&&ch!='0') ch=getchar();

    if (ch=='-') w=0,ch=getchar();

    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return w?x:-x;

}

const int N = 4005;

const int inf = 1e9;

struct edge{int to,nxt,w;}a[N*30];

int n,m,s,t,head[N],cnt=1,dep[N],cur[N],dfn[N],low[N],vis[N],Stack[N],top,bel[N],scc;

queue<int>Q;

void link(int u,int v,int w)

{

    a[++cnt]=(edge){v,head[u],w};

    head[u]=cnt;

    a[++cnt]=(edge){u,head[v],0};

    head[v]=cnt;

}

bool bfs()

{

    memset(dep,0,sizeof(dep));

    dep[s]=1;Q.push(s);

    while (!Q.empty())

    {

        int u=Q.front();Q.pop();

        for (int e=head[u];e;e=a[e].nxt)

            if (a[e].w&&!dep[a[e].to])

                dep[a[e].to]=dep[u]+1,Q.push(a[e].to);

    }

    return dep[t];

}

int dfs(int u,int f)

{

    if (u==t) return f;

    for (int &e=cur[u];e;e=a[e].nxt)

        if (a[e].w&&dep[a[e].to]==dep[u]+1)

        {

            int tmp=dfs(a[e].to,min(a[e].w,f));

            if (tmp) {a[e].w-=tmp;a[e^1].w+=tmp;return tmp;}

        }

    return 0;

}

void Dinic()

{

    while (bfs())

    {

        for (int i=1;i<=n;++i) cur[i]=head[i];

        while (dfs(s,inf)) ;

    }

}

void Tarjan(int u)

{

    dfn[u]=low[u]=++cnt;

    Stack[++top]=u;vis[u]=1;

    int v;

    for (int e=head[u];e;e=a[e].nxt)

        if (a[e].w)

        {

            v=a[e].to;

            if (!dfn[v]) Tarjan(v),low[u]=min(low[u],low[v]);

            else if (vis[v]) low[u]=min(low[u],dfn[v]);

        }

    if (dfn[u]==low[u])

    {

        ++scc;

        do{

            v=Stack[top--];

            vis[v]=0;bel[v]=scc;

        }while (u!=v);

    }

}

int main()

{

    n=gi();m=gi();s=gi();t=gi();

    for (int i=1;i<=m;++i)

    {

        int u=gi(),v=gi(),w=gi();

        link(u,v,w);

    }

    Dinic();cnt=0;

    for (int i=1;i<=n;++i) if (!dfn[i]) Tarjan(i);

    for (int i=1;i<=m;++i)

    {

        int u=a[i<<1|1].to,v=a[i<<1].to;

        printf("%d ",bel[u]!=bel[v]&&!a[i<<1].w);

        printf("%d\n",bel[u]==bel[s]&&bel[v]==bel[t]);

    }

    return 0;

}