cogs 1274 最小截断
题解：
最小割唯一判定，即判断每条边是否可以在最小割中以及是否一定在最小割中。
理由我也不懂，方法是先跑一个最小割，然后在残余网络上跑Tarjan。然后枚举每一条边，如果该边没满流，那么永远不会出现在最小割的边集中。否则如果Id[fr]=Id[to]，该边也不会出现在最小割边集中，它只不过是恰好被跑满流而已。如果Id[fr]!=Id[to]，那么该边可以出现在割集中。更进一步，如果Id[fr]=Id[S],Id[to]=Id[T]，那么该边一定出现在割集中。
没去看证明。假装我知道它是对的。
网上证明：
① <==将每个SCC缩成一个点，得到的新图就只含有满流边了。那么新图的任一s-t割都对应原图的某个最小割，从中任取一个把id[u]和id[v]割开的割即可证明。
② <==：假设将(u,v)的边权增大，那么残余网络中会出现s->u->v->t的通路，从而能继续增广，于是最大流流量（也就是最小割容量）会增大。这即说明(u,v)是最小割集中必须出现的边。
三倍经验cogs 426 血帆海盗，cogs 2669 新型城市化
需要注意一下，因为这两道题都是二分图，与S和T相连的边的容量应该设为INF而不是1，设为1虽然可以跑出最大流，但是割集的元素就不仅仅是二分图上的边了，还会有从S出发的边。如果强行设成1，对于满流的边好像只要Id[fr]!=Id[to]则一定是割集上的边。。。
code
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define fcl fclose(stdin); fclose(stdout); return 0
const int INF=0x3f3f3f3f;
void Read(int& x){
char ch; while(ch=getchar(),ch<'0'||ch>'9');
x=ch-'0'; while(ch=getchar(),ch>='0'&&ch<='9') x=x*10+ch-'0';
}
int n,m,S,T;
struct EDGE{
int to,next,cap,flow;
}edge[120010];
int head[4010],tot=1;
#define ty (edge[x].to)
inline void AddEdge(int a,int b,int c){
edge[++tot].to=b;
edge[tot].cap=c;
edge[tot].flow=0;
edge[tot].next=head[a];
head[a]=tot;
}
inline void Add(int a,int b,int c){
AddEdge(a,b,c); AddEdge(b,a,0);
}
int ans1[60010],ans2[60010];
int dis[4010],Q[4010],cur[4010];
bool Bfs(){
memset(dis,0x3f,(n+1)<<2);
dis[S]=0;
int s=1,t=0,u; Q[++t]=S;
while(s<=t){
u=Q[s++];
for(int x=head[u];x;x=edge[x].next)
if(edge[x].cap>edge[x].flow&&dis[ty]==INF)
dis[ty]=dis[u]+1,Q[++t]=ty;
}
return dis[T]!=INF;
}
int Dfs(int u,int a){
if(u==T||a==0) return a;
int f2=0,f;
for(int& x=cur[u];x;x=edge[x].next){
if(edge[x].cap>edge[x].flow&&dis[ty]==dis[u]+1){
f=Dfs(ty,min(a,edge[x].cap-edge[x].flow));
edge[x].flow+=f; edge[x^1].flow-=f;
f2+=f; a-=f;
if(a==0) break;
}
}
return f2;
}
void MaxFlow(){
int q=0;
while(Bfs()){
memcpy(cur,head,(n+1)<<2);Dfs(S,INF);
}
}
int dfn[4010],low[4010],ti=0;
int Fa[4010],sta[4010],siz=0;
int flag[4010];
void Tarjan(int u){
dfn[u]=low[u]=++ti;
flag[u]=1; sta[++siz]=u;
for(int x=head[u];x;x=edge[x].next){
if(edge[x].cap==edge[x].flow) continue;
if(flag[ty]==1) low[u]=min(low[u],dfn[ty]);
else if(flag[ty]==0){
Tarjan(ty);
low[u]=min(low[u],low[ty]);
}
}
if(dfn[u]==low[u]){
while(1){
Fa[sta[siz]]=u;
flag[sta[siz]]=2;
if(sta[siz--]==u) break;
}
}
}
int main(){
freopen("mincut.in","r",stdin);
freopen("mincut.out","w",stdout);
Read(n); Read(m); Read(S); Read(T);
int x,y,c;
for(int i=1;i<=m;++i){
Read(x); Read(y); Read(c);
Add(x,y,c);
}
MaxFlow();
for(int i=1;i<=n;++i)
if(!flag[i]) Tarjan(i);
for(int i=1;i<=n;++i){
for(int x=head[i];x;x=edge[x].next){
if(x&1) continue;
if(edge[x].cap==edge[x].flow){
if(Fa[i]==Fa[ty]) continue;
ans1[x>>1]=1;
if(Fa[i]==Fa[S]&&Fa[ty]==Fa[T]) ans2[x>>1]=1;
}
}
}
for(int i=1;i<=m;++i) printf("%d %d
",ans1[i],ans2[i]);
fcl;
}