BZOJ_1797_[Ahoi2009]Mincut 最小割_最小割+tarjan
Description
A,B两个国家正在交战，其中A国的物资运输网中有N个中转站，M条单向道路。设其中第i (1≤i≤M)条道路连接了vi,ui两个中转站，那么中转站vi可以通过该道路到达ui中转站，如果切断这条道路，需要代价ci。现在B国想找出一个路径切断方案，使中转站s不能到达中转站t，并且切断路径的代价之和最小。 小可可一眼就看出，这是一个求最小割的问题。但爱思考的小可可并不局限于此。现在他对每条单向道路提出两个问题： 问题一：是否存在一个最小代价路径切断方案，其中该道路被切断？ 问题二：是否对任何一个最小代价路径切断方案，都有该道路被切断？ 现在请你回答这两个问题。
Sample Input
6 7 1 6
1 2 3
1 3 2
2 4 4
2 5 1
3 5 5
4 6 2
5 6 3
1 2 3
1 3 2
2 4 4
2 5 1
3 5 5
4 6 2
5 6 3
Sample Output
1 0
1 0
0 0
1 0
0 0
1 0
1 0
首先求一遍最小割，然后在残量网络缩点。显然有S，T不在同一强连通分量中。
考虑边(u,v) ，如果u和v在同一scc中，那么割去这条边后仍有通路,因此它不会出现在任何一边的割集当中。
如果S和u在同一scc并且v和T在同一scc，那么假设在这条边上多加一些流量，那么从S到T则又可以增广，因此它一定会被割掉。
如果这条边没有满流，它同样不会被割掉。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 5000
#define M 120050
#define inf 100000000
#define mem(x) memset(x,0,sizeof(x));
int head[N],to[M],nxt[M],flow[M],n,m,cnt=1;
int dep[N],Q[N],l,r,S,T;
int St[N],top,ins[N],bl[N],scc,tot,dfn[N],low[N];
inline void add(int u,int v,int f){
to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;flow[cnt]=f;
}
bool bfs(){
l=r=0;
mem(dep);
Q[r++]=S;dep[S]=1;
while(l<r){
int x=Q[l++];
for(int i=head[x];i;i=nxt[i]){
if(!dep[to[i]]&&flow[i]){
dep[to[i]]=dep[x]+1;
if(to[i]==T)return 1;
Q[r++]=to[i];
}
}
}return 0;
}
int dfs(int x,int mf){
if(x==T)return mf;
int nf=0;
for(int i=head[x];i;i=nxt[i]){
if(dep[to[i]]==dep[x]+1&&flow[i]){
int tmp=dfs(to[i],min(mf-nf,flow[i]));
nf+=tmp;
flow[i]-=tmp;
flow[i^1]+=tmp;
if(nf==mf)break;
}
}
dep[x]=0;return nf;
}
void dinic(){
int ans=0,f=0;
while(bfs()){
while(f=dfs(S,inf)){
ans+=f;
}
}
}
void tarjan(int x){
dfn[x]=low[x]=++tot;
St[top++]=x;ins[x]=1;
for(int i=head[x];i;i=nxt[i]){
if(flow[i]==0)continue;
if(!dfn[to[i]]){
tarjan(to[i]);
low[x]=min(low[x],low[to[i]]);
}else if(!bl[to[i]]){
low[x]=min(low[x],dfn[to[i]]);
}
}
if(low[x]==dfn[x]){
int t=St[--top];ins[t]=0;
bl[t]=++scc;
while(t^x){
t=St[--top];ins[t]=0;
bl[t]=scc;
}
}
}
int main(){
scanf("%d%d%d%d",&n,&m,&S,&T);
int x,y,z;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);add(y,x,0);
}
dinic();
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i);
}
for(int i=1;i<=m;i++){
if(flow[i<<1]){
printf("0 0
");continue;
}
int g=to[i<<1|1],h=to[i<<1];
printf("%d %d
",bl[g]!=bl[h],bl[g]==bl[S]&&bl[h]==bl[T]);
/*if(bl[g]!=bl[h])printf("1");
else printf("0");
if(bl[g]==bl[S]&&bl[h]==bl[T])printf(" 1
");
else printf(" 0
");*/
}
}