求最大流，在残余网络上跑tarjan求出所有SCC，记id[u]为点u所在SCC的编号。显然有id[s]!=id[t]（否则s到t有通路，能继续增广）。
①对于任意一条满流边(u,v)，(u,v)能够出现在某个最小割集中，当且仅当id[u]!=id[v]；②对于任意一条满流边(u,v)，(u,v)必定出现在最小割集中，当且仅当id[u]==id[s]且id[v]==id[t]。#include#include #include #include #include using namespace std;#define maxn 4200#define maxm 130000#define inf 0x3fffffffint e[maxn],ne[maxm],v[maxm],u[maxm];int nn=1;void add(int x,int y,int uu){ ne[++nn]=e[x],e[x]=nn,v[nn]=y,u[nn]=uu; }int s,t,n,m,ch[maxn];int x,qu[maxn],he,bo,low[maxn],stn,st[maxn],dfn[maxn],been[maxn];bool bfs(){ memset(ch,-1,sizeof(ch)); ch[qu[he=bo=1]=s]=0; while(he>=bo)for(int i=e[x=qu[bo++]];i;i=ne[i])if(ch[v[i]]==-1&&u[i])qu[++he]=v[i],ch[v[i]]=ch[x]+1; return ch[t]==-1;} int zeng(int no,int mm){ if(no==t)return mm; int k,r=mm; for(int i=e[no];i&&r;i=ne[i])if(u[i]&&ch[v[i]]==ch[no]+1){ k=zeng(v[i],min(r,u[i])); u[i]-=k,u[i^1]+=k,r-=k; } if(r==mm)return ch[no]=-1,0; return mm-r;}int tot,in[maxn],kk;void tarjan(int x){ dfn[x]=low[x]=++tot; been[st[++stn]=x]=1; for(int i=e[x];i;i=ne[i])if(u[i]) if(!dfn[v[i]]){ tarjan(v[i]); low[x]=min(low[x],low[v[i]]); }else if(been[v[i]])low[x]=min(low[x],dfn[v[i]]); if(low[x]==dfn[x]){ kk++; do{ in[st[stn]]=kk; been[st[stn]]=0; }while(st[stn--]!=x); }}int main(){ scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1;i<=m;i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); add(b,a,0); } while(!bfs())while(zeng(s,inf)); for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i); for(int i=1;i<=m;i++){ if(in[v[i<<1]]!=in[v[(i<<1)+1]]&&!u[(i<<1)])printf("1 "); else printf("0 "); if(in[v[i<<1]]==in[t]&&in[v[(i<<1)+1]]==in[s]&&!u[(i<<1)])printf("1\n"); else printf("0\n"); } }