来自FallDream的博客，未经允许，请勿转载，谢谢qaq
A,B两个国家正在交战，其中A国的物资运输网中有N个中转站，M条单向道路。设其中第i (1≤i≤M)条道路连接了vi,ui两个中转站，那么中转站vi可以通过该道路到达ui中转站，如果切断这条道路，需要代价ci。现在B国想找出一个路径切断方案，使中转站s不能到达中转站t，并且切断路径的代价之和最小。 小可可一眼就看出，这是一个求最小割的问题。但爱思考的小可可并不局限于此。现在他对每条单向道路提出两个问题： 问题一：是否存在一个最小代价路径切断方案，其中该道路被切断？ 问题二：是否对任何一个最小代价路径切断方案，都有该道路被切断？ 现在请你回答这两个问题。
n<=4000 m<=60000
题解：先跑一次最小割，然后在残量网络上tarjan，用所有没满流的边缩点。
由于是最小割，所以显然ST不在同一块
一条边如果没有满流，那么它就不可能被割了。在这基础上：
一条边可以被割当且仅当连接的两个点所属的块不同。
一条边一定被割当且仅当连接的两个点分别和S,T同块。
证明我不会，转一个鏼爷(jcvb)的题解：
<==将每个SCC缩成一个点，得到的新图就只含有满流边了。那么新图的任一s-t割都对应原图的某个最小割，从中任取一个把id[u]和id[v]割开的割即可证明。
< ==：假设将(u,v)的边权增大，那么残余网络中会出现s->u->v->t的通路，从而能继续增广，于是最大流流量（也就是最小割容量）会增大。这即说明(u,v)是最小割集中必须出现的边。
#include<iostream> #include<cstdio> #include<cstring> #define ll long long #define MN 4000 #define INF 2000000000 using namespace std; inline 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; } int n,m,S,T,head[MN+5],cnt=1,d[MN+5],c[MN+5],q[MN+5],top,dn=0,dfn[MN+5],low[MN+5],bel[MN+5],cc=0; struct edge{int from,to,next,w;}e[120005]; inline void ins(int f,int t,int w) { e[++cnt]=(edge){f,t,head[f],w};head[f]=cnt; e[++cnt]=(edge){t,f,head[t],0};head[t]=cnt; } int dfs(int x,int f) { if(x==T)return f; int used=0; for(int&i=c[x];i;i=e[i].next) if(e[i].w&&d[e[i].to]==d[x]+1) { int w=dfs(e[i].to,min(f-used,e[i].w)); used+=w;e[i].w-=w;e[i^1].w+=w; if(used==f)return used; } return d[x]=-1,used; } bool bfs() { memset(d,0,sizeof(d));int i,j; for(d[q[top=i=1]=S]=1;i<=top;i++) for(j=c[q[i]]=head[q[i]];j;j=e[j].next) if(e[j].w&&!d[e[j].to]) d[q[++top]=e[j].to]=d[q[i]]+1; return d[T]; } void tarjan(int x) { dfn[x]=low[x]=++dn;q[++top]=x; for(int i=head[x];i;i=e[i].next) if(e[i].w) { if(!dfn[e[i].to]) tarjan(e[i].to),low[x]=min(low[x],low[e[i].to]); else if(!bel[e[i].to]) low[x]=min(low[x],dfn[e[i].to]); } if(dfn[x]==low[x]) for(++cc;q[top+1]!=x;--top) bel[q[top]]=cc; } int main() { n=read();m=read();S=read();T=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(),c=read(); ins(u,v,c); } while(bfs()) dfs(S,INF); top=0; memset(q,0,sizeof(q)); for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); for(int i=2;i<=cnt;i+=2) printf("%d %d ",!e[i].w&&bel[e[i].from]!=bel[e[i].to],bel[e[i].from]==bel[S]&&bel[e[i].to]==bel[T]); return 0; }