bzoj 1797[Ahoi 2009]Mincut最小割最小割出力方式

Description
A,B両国は交戦しており,そのうちA国の物資輸送網にはNの中継所があり,M本の一方通行道路がある.i番目(1≦i≦M)の道路がvi,uiの2つの中継局を接続しているとすると、中継局viはその道路を通ってui中継局に到達することができ、この道路を切断すると、代価ciが必要となる.現在、B国は、中継局sが中継局tに到達できず、経路を切断する代価の和を最小限に抑える経路切断案を見つけようとしている.可ちゃんは一目で分かるように、これは最小割を求める問題だ.しかし、考えるのが好きなのはそれに限らない.今、彼は各一方向道路に対して2つの問題を提出した:問題1:最小代価経路切断案が存在し、その中でこの道路が切断されているかどうか.問題2:いずれかの最小代価経路切断案に対して、この道路が切断されているかどうか.今、この二つの質問に答えてください.
Solution
今になってからシナリオを出力します.以前は削除しながらm回の最大ストリームを走るだけでした
最大ストリームを1回走って残量ネットワークを得て、私たちは不満ストリームの辺をほじくり出して連通成分を強く走って、それでは縮小して残りの辺はすべて満流辺です.まず不満の流れの辺はきっとあり得ません

エッジ(u,v)が最小ダイバーシティに現れる可能性がある場合、scc[u]!=scc[v]

エッジ(u,v)が必ず最小ダイバーシティに現れると、(scc[u]=scc[s])、および(scc[v]=scc[t])

2比較は明らかに1の場合、残りのエッジが切断されているため、(scc[u],scc[v])を含む集合を選択して切断するだけでよい.
Code

#include 
#include 
#include 
#include 
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define fill(x,t) memset(x,t,sizeof(x))

const int INF=0x3f3f3f3f;
const int N=200005;
const int E=500005;

struct edge {int x,y,w,next;} e[E];

int dis[N],stack[N],dfn[N],low[N],top;
int ls[N],scc[N],edCnt=1;

bool vis[N];

int read() {
	int x=0,v=1; char ch=getchar();
	for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
	for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
	return x*v;
}

void add_edge(int x,int y,int w) {
	e[++edCnt]=(edge) {x,y,w,ls[x]}; ls[x]=edCnt;
	e[++edCnt]=(edge) {y,x,0,ls[y]}; ls[y]=edCnt;
}

bool bfs(int st,int ed) {
	std:: queue <int> que;
	fill(dis,0); dis[st]=1;
	for (que.push(st);!que.empty();) {
		int x=que.front(); que.pop();
		for (int i=ls[x];i;i=e[i].next) {
			if (e[i].w>0&&dis[e[i].y]==0) {
				dis[e[i].y]=dis[x]+1;
				if (e[i].y==ed) return true;
				que.push(e[i].y);
			}
		}
	}
	return false;
}

int find(int x,int ed,int mn) {
	if (x==ed||!mn) return mn;
	int ret=0;
	for(int i=ls[x];i;i=e[i].next) {
		if (e[i].w>0&&dis[x]+1==dis[e[i].y]) {
			int d=find(e[i].y,ed,std:: min(mn-ret,e[i].w));
			e[i].w-=d; e[i^1].w+=d; ret+=d;
			if (mn==ret) break;
		}
	}
	return ret;
}

int dinic(int st,int ed) {
	int res=0;
	for (;bfs(st,ed);) res+=find(st,ed,INF);
	return res;
}

void dfs(int x) {
	stack[++top]=x; vis[x]=1;
	dfn[x]=low[x]=++dfn[0];
	for (int i=ls[x];i;i=e[i].next) {
		if (!e[i].w) continue;
		if (!dfn[e[i].y]) {
			dfs(e[i].y);
			low[x]=std:: min(low[x],low[e[i].y]);
		} else if (vis[e[i].y]) {
			low[x]=std:: min(low[x],dfn[e[i].y]);
		}
	}
	if (low[x]==dfn[x]) {
		int y=0; scc[0]++;
		while (y!=x) {
			y=stack[top--];
			scc[y]=scc[0];
			vis[y]=0;
		}
	}
}

int main(void) {
	int n=read(),m=read(),s=read(),t=read();
	rep(i,1,m) {
		int x=read(),y=read(),w=read();
		add_edge(x,y,w);
	}
	dinic(s,t);
	rep(i,1,n) if (!dfn[i]) dfs(i);
	for (int i=2;i<=edCnt;i+=2) {
		if (e[i].w) {puts("0 0"); continue;}
		printf("%d ", (scc[e[i].x]!=scc[e[i].y]));
		printf("%d
", (scc[e[i].x]==scc[s])&&(scc[e[i].y]==scc[t]));
	}
	return 0;
}