Description:

求S-T的有向图中，哪些边可能会出现在最小割集里，哪些边必定会出现在最小割集里。

Solution:

跑一遍最大流，在残余网络中求SCC，对于所有的满流边(u,v)：

1. 若belong[u] != belong[v]，则边(u,v)可能出现在最小割集中；
2. 若belong[u] == belong[s], belong[v] == belong[t], 则边(u,v)必定出现在最小割集中。

Analysis:

出现在最小割集中边一定是满流边

对于所有满流边：

1.1.若belong[u] == belong[v]则（以下By jcvb）残余网络存在u->v的通路，通过(u,v)的割也必然通过这条路径上的非满流边，不会是最小割(据说是错的- -)

1.2.若belong[u] != belong[v]则把所有SCC缩成一个点后构成的新图只存在满流边，那么新图中的任S-T割都是原图的最小割，所以都是可能出现在最小割集中的边

2.1.若将(u,v)的边权增大，那么就存在了S->u->v->T的一条增广路，于是最大流容量(最小割容量)也就增大了，所以(u,v)一定是出现在最小割集中的边

2.2.反推显然

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 4010, MAXM = 60010;
struct Eg
{
	int v, z, id; Eg *ne, *ep;
} e[MAXM * 2], *G = e, *po[MAXN], *la[MAXN];
int N, M, S, T, flow, Be, top, tot, ans[MAXM][2];
int d[MAXN], num[MAXN], dfn[MAXN], low[MAXN], belong[MAXN], q[MAXN], f[MAXN];
void add(int a, int b, int c, int id)
{
	G->v = b; G->z = c; G->id = id; G->ep = G+1; G->ne = po[a]; po[a] = G++;
	G->v = a; G->z = 0; G->id =  0; G->ep = G-1; G->ne = po[b]; po[b] = G++;
}
int dfs(int x, int f)
{
	if(x == T) return f; int r = 0;
	for(Eg *j = la[x]; j; j = j->ne)
	if(j->z > 0 && d[j->v] + 1 == d[x])
	{
		la[x] = j; int p = dfs(j->v, min(j->z, f - r));
		j->z -= p; j->ep->z += p; if(f == (r += p)) return r;
	}
	if(d[S] >= N) return r;
	if(!--num[d[x]]) d[S] = N;
	++num[++d[x]]; la[x] = po[x];
	return r;
}
void Dfs(int x)
{
	f[q[++top] = x] = dfn[x] = low[x] = ++tot;
	for(Eg *j = po[x]; j; j = j->ne) if(j->z > 0)
		if(!dfn[j->v]) Dfs(j->v), low[x] = min(low[x], low[j->v]);
		else if(f[j->v]) low[x] = min(low[x], dfn[j->v]);
	if(dfn[x] == low[x])
	{
		for(++Be; q[top] != x; )
			belong[q[top]] = Be, f[q[top--]] = 0;
		belong[x] = Be; f[x] = 0; --top;
	}
}
int main()
{
	scanf("%d%d%d%d", &N, &M, &S, &T);
	for(int i = 1, a, b, c; i <= M; ++i)
		scanf("%d%d%d", &a, &b, &c), add(a, b, c, i);
	for(int i = 1; i <= N; ++i) la[i] = po[i];
	num[0] = N; while(d[S] < N) flow += dfs(S, ~0U>>1);
	for(int i = 1; i <= N; ++i) if(!dfn[i]) Dfs(i);
	for(int i = 1; i <= N; ++i)
		for(Eg *j = po[i]; j; j = j->ne)
		if(j->z == 0 && j->id != 0)
		{
			if(belong[i] != belong[j->v]) ans[j->id][0] = 1;
			if(belong[i] == belong[S] && belong[j->v] == belong[T]) ans[j->id][1] = 1;
		}
	for(int i = 1; i <= M; ++i) printf("%d %d\n", ans[i][0], ans[i][1]);
	return 0;
}