题意

给出一个有向图，问哪些边一定存在最小割中，哪些边可能存在于最小割中。 n<=4000,m<=60000

分析

首先对原图跑最大流，得到残余网络。 很容易得知若一条边u->v存在u->v的增广路，则这条边一定不是割边，反之亦然则可能是割边。 那么我们就把点分成了s集和t集还有一部分不确定。若一条边连接了s集和t集，则这条边一定是必然存在度最小割中的边。

那么我们就得到了这样一个算法： 把残余网络中每个SCC缩成一个点，这样图中剩下的边则必然是满流边，且图中的每一个割都对应了原图中的一个最小割。设点i所在的强连通分量为id[i].那么一条边可能存在于割集中当且仅当id[u]!=id[v]。一条边一定存在于割集中当且仅当id[u]==id[s]且id[v]==id[t]。

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=4005; const int M=60005; int n,m,s,t,cnt,last[N],cur[N],dfn[N],low[N],tim,sta[N],top,dis[N],tot,id[N]; bool ins[N]; struct edge{int to,next,c;}e[M*2]; queue<int> que; int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } void addedge(int u,int v,int c) { e[++cnt].to=v;e[cnt].c=c;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].c=0;e[cnt].next=last[v];last[v]=cnt; } bool bfs() { for (int i=1;i<=n;i++) dis[i]=0; while (!que.empty()) que.pop(); dis[s]=1;que.push(s); while (!que.empty()) { int u=que.front();que.pop(); for (int i=last[u];i;i=e[i].next) if (e[i].c&&!dis[e[i].to]) { dis[e[i].to]=dis[u]+1; if (e[i].to==t) return 1; que.push(e[i].to); } } return 0; } int dfs(int x,int maxf) { if (x==t|!maxf) return maxf; int ret=0; for (int &i=cur[x];i;i=e[i].next) if (e[i].c&&dis[e[i].to]==dis[x]+1) { int f=dfs(e[i].to,min(e[i].c,maxf-ret)); e[i].c-=f; e[i^1].c+=f; ret+=f; if (maxf==ret) break; } return ret; } void dinic() { while (bfs()) { for (int i=1;i<=n;i++) cur[i]=last[i]; dfs(s,1000000000); } } void tarjan(int x) { dfn[x]=low[x]=++tim; ins[x]=1;sta[++top]=x; for (int i=last[x];i;i=e[i].next) { if (!e[i].c) continue; if (!dfn[e[i].to]) { tarjan(e[i].to); low[x]=min(low[x],low[e[i].to]); } else if (ins[e[i].to]) low[x]=min(low[x],dfn[e[i].to]); } if (low[x]==dfn[x]) { tot++;int y=sta[top--];id[y]=tot;ins[y]=0; while (y!=x) y=sta[top--],id[y]=tot,ins[y]=0; } } int main() { n=read();m=read();s=read();t=read();cnt=1; for (int i=1;i<=m;i++) { int x=read(),y=read(),z=read(); addedge(x,y,z); } dinic(); for (int i=1;i<=n;i++) if (!dfn[i]) tarjan(i); for (int i=2;i<=cnt;i+=2) if (e[i].c) puts("0 0"); else { if (id[e[i].to]!=id[e[i^1].to]) printf("1 "); else printf("0 "); if (id[e[i].to]==id[t]&&id[e[i^1].to]==id[s]) puts("1"); else puts("0"); } return 0; }