P4126 [AHOI2009]最小割

题意

这题加深了我对最小割的理解

先跑最大流,求出残留网络,对残留网络进行求SCC

源点和汇点显然不在同一个SCC中,不然就有增广路了

考虑每一条边\((u,v)\)

要成为最小割的边首先要满流(参见最大流最小割定理的推论)

1.如果u和源点在一个scc中,v和汇点在一个SCC中那么这条边是必须边

2.如果u和v不在同一个scc中,那么这条边为可行边

code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=4010;
const int maxm=60010;
const int inf=1e9;
int n,m,cnt=1,st,ed,top,tot,tim;
int head[maxn],cur[maxn],dep[maxn],dfn[maxn],low[maxn],sta[maxn],col[maxn];
bool vis[maxn];
struct edge{int to,nxt,flow;}e[maxm<<1];
inline void add(int u,int v,int w)
{
    e[++cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].to=v;
    e[cnt].flow=w;
}
inline bool bfs()
{
    memset(dep,0,sizeof(dep));
    for(int i=1;i<=n;i++)cur[i]=head[i];
    queue<int>q;
    q.push(st);dep[st]=1;
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(int i=head[x];i;i=e[i].nxt)
        {
            int y=e[i].to;
            if(dep[y]||e[i].flow<=0)continue;
            dep[y]=dep[x]+1;q.push(y);
        }
    }
    return dep[ed]>0;
}
int dfs(int x,int goal,int lim)
{
    if(x==goal||lim<=0)return lim;
    int res=lim;
    for(int i=cur[x];i;i=e[i].nxt)
    {
        cur[x]=i;
        int y=e[i].to;
        if(dep[y]!=dep[x]+1||e[i].flow<=0)continue;
        int tmp=dfs(y,goal,min(res,e[i].flow));
        if(tmp<=0)dep[y]=0;
        res-=tmp;
        e[i].flow-=tmp,e[i^1].flow+=tmp;
        if(res<=0)break;
    }
    return lim-res;
}
inline int Dinic()
{
    int res=0;
    while(bfs())res+=dfs(st,ed,inf);
    return res;
}
void tarjan(int x)
{
    dfn[x]=low[x]=++tim;
    sta[++top]=x;vis[x]=1;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(e[i].flow<=0)continue;
        if(!dfn[y])tarjan(y),low[x]=min(low[x],low[y]);
        else if(vis[y])low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x])
    {
        tot++;int y;
        do
        {
            y=sta[top--];vis[y]=0;col[y]=tot;
        }while(y!=x);
    }
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&st,&ed);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;scanf("%d%d%d",&u,&v,&w);
        add(u,v,w),add(v,u,0);
    }
    Dinic();
    for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
    for(int i=2;i<=cnt;i+=2)
    {
        if(e[i].flow>0){puts("0 0");continue;}
        int x=e[i^1].to,y=e[i].to;
        if(col[x]!=col[y])printf("1 ");
        else printf("0 ");
        if(col[x]==col[st]&&col[y]==col[ed])printf("1\n");
        else printf("0\n");
    }
    return 0;
}

P4126 [AHOI2009]最小割

原文：https://www.cnblogs.com/nofind/p/12089676.html