记录编号	155966	评测结果	AAAAAAAAAA
题目名称	[AHOI2009] 最小截断	最终得分	100
用户昵称	RP++	是否通过	通过
代码语言	C++	运行时间	0.186 s
提交时间	2015-04-01 11:01:29	内存使用	2.70 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>

using namespace std;

#define maxn 4010
#define maxm 120010
#define INF 0x3fffffff

stack<int>S;

int tot = 1, n, m, s, t, scc, dfs_clock;
int to[maxm], next[maxm], cap[maxm], head[maxn], cur[maxn], pre[maxn], dfn[maxn], low[maxn];
int belong[maxn], ans[maxm][2];
bool vis[maxn], flag[maxn];

void Build(int s, int t, int v) {
	to[++tot] = t, next[tot] = head[s], cap[tot] = v, head[s] = tot;
	to[++tot] = s, next[tot] = head[t], cap[tot] = 0, head[t] = tot;
}

bool BFS() {
	for(int i =1; i <= n; i++) vis[i] = false;
	queue<int>q; q.push(s);
	pre[s] = 0, vis[s] = true;
	while(!q.empty()) {
		int p = q.front(); q.pop();
		for(int i = head[p]; i; i = next[i]) {
			int l = to[i];
			if(!cap[i] || vis[l]) continue;
			vis[l] = true, pre[l] = pre[p] + 1, q.push(l);
		}
	}
	return vis[t];
}

int DFS(int u, int mmin) {
	if(u == t || mmin == 0) return mmin;
	int flow = 0, f;
	for(int& i = cur[u]; i; i = next[i]) {
		int l = to[i];
		if(pre[l] == pre[u] + 1 && (f = DFS(l, min(mmin, cap[i]))) > 0) {
			mmin -= f, flow += f, cap[i] -= f, cap[i^1] += f;
			if(mmin == 0) break;
		}
	}
	return flow;
}

void tarjan(int x) {
	low[x]=dfn[x]=++dfs_clock;
	S.push(x); flag[x]=true;
	for(int i=head[x];i;i=next[i]) {
		int l=to[i];
		if(!cap[i]) continue; 
		if(!dfn[l]) tarjan(l),low[x]=min(low[x],low[l]);
		else if(flag[l]) low[x]=min(low[x],dfn[l]);
	}
	if(dfn[x]==low[x]) {
		int tmp=-1; scc++;
		while(tmp!=x) {
			tmp=S.top(); S.pop();
			belong[tmp]=scc, flag[tmp]=false;
		}
	}
}

int main() {
	freopen("mincut.in", "r", stdin);
	freopen("mincut.out", "w", stdout);
	scanf("%d%d%d%d", &n, &m, &s, &t);
	for(int i = 1, x, y, z; i <= m; i++) {
		scanf("%d%d%d", &x, &y, &z);
		Build(x, y, z);
	}
	while(BFS()) {
		memcpy(cur, head, sizeof(head));
		DFS(s, INF);
	}
	for(int i = 1; i <= n; i++)
		if(!dfn[i]) tarjan(i);
	for(int i = 1; i <= n; i++) {
		for(int j = head[i]; j; j = next[j]) {
			if(j & 1) continue;
			int l = to[j];
			if(belong[i] != belong[l] && cap[j] == 0) ans[j>>1][0] = 1;
			if(belong[i] == belong[s] && belong[l] == belong[t] && cap[j] == 0) ans[j>>1][1] = 1;
		}
	}
	for(int i = 1; i <= m; i++)
		printf("%d %d\n", ans[i][0], ans[i][1]);
}