先跑dinic，然后对残量网络做tarjan。对于一条边：
若两顶点分属两个强联通分量，那么可能是割。
若两顶点分属S,T所在的强联通分量，那么一定是割。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define maxv 4050 #define maxe 120050 #define inf 1000000007 using namespace std; int n,m,s,t,x[maxe],y[maxe],z[maxe],g[maxv],nume=1,st[maxv],top=0,dfn[maxv],low[maxv],max_flow=0,id[maxv]; int tot=0,times=0,dis[maxv]; struct edge { int v,f,nxt; }e[maxe]; bool vis[maxv],ins[maxv]; queue <int> q; void addedge(int u,int v,int f) { e[++nume].v=v;e[nume].f=f;e[nume].nxt=g[u];g[u]=nume; e[++nume].v=u;e[nume].f=0;e[nume].nxt=g[v];g[v]=nume; } bool bfs() { for (int i=1;i<=n;i++) dis[i]=inf; dis[s]=0;q.push(s); while (!q.empty()) { int head=q.front();q.pop(); for (int i=g[head];i;i=e[i].nxt) { int v=e[i].v; if (dis[v]>dis[head]+1 && e[i].f>0) { dis[v]=dis[head]+1; q.push(v); } } } return dis[t]!=inf; } int dinic(int x,int low) { if (x==t) return low; int ret=0; for (int i=g[x];i && low;i=e[i].nxt) { int v=e[i].v; if (e[i].f>0 && dis[v]==dis[x]+1) { int dd=dinic(v,min(low,e[i].f)); low-=dd;ret+=dd;e[i].f-=dd;e[i^1].f+=dd; } } if (!ret) dis[x]=inf; return ret; } void tarjan(int x) { vis[x]=true;ins[x]=true;dfn[x]=low[x]=++times;st[++top]=x; for (int i=g[x];i;i=e[i].nxt) { int v=e[i].v; if (e[i].f<=0) continue; if (!vis[v]) {tarjan(v);low[x]=min(low[x],low[v]);} else if (ins[v]) low[x]=min(low[x],dfn[v]); } if (dfn[x]==low[x]) { ++tot;int ret; do { ret=st[top]; top--;ins[ret]=false;id[ret]=tot; }while (top && ret!=x); } } int main() { scanf("%d%d%d%d",&n,&m,&s,&t); for (int i=1;i<=m;i++) { scanf("%d%d%d",&x[i],&y[i],&z[i]); addedge(x[i],y[i],z[i]); } while (bfs()) max_flow+=dinic(s,inf); for (int i=1;i<=n;i++) if (!vis[i]) tarjan(i); for (int i=1;i<=m;i++) { if (e[i<<1].f>0) printf("0 0 "); else if (id[x[i]]!=id[y[i]]) { if (id[x[i]]==id[s] && id[y[i]]==id[t]) printf("1 1 "); else printf("1 0 "); } else printf("0 0 "); } return 0; }