A,B两个国家正在交战，其中A国的物资运输网中有N个中转站，M条单向道路。设其中第i (1≤i≤M)条道路连接了vi,ui两个中转站，那么中转站vi可以通过该道路到达ui中转站，如果切断这条道路，需要代价ci。现在B国想找出一个路径切断方案，使中转站s不能到达中转站t，并且切断路径的代价之和最小。 小可可一眼就看出，这是一个求最小割的问题。但爱思考的小可可并不局限于此。现在他对每条单向道路提出两个问题： 问题一：是否存在一个最小代价路径切断方案，其中该道路被切断？ 问题二：是否对任何一个最小代价路径切断方案，都有该道路被切断？ 现在请你回答这两个问题。
第一行有4个正整数，依次为N,M,s和t。第2行到第(M+1)行每行3个正 整数v,u,c表示v中转站到u中转站之间有单向道路相连，单向道路的起点是v， 终点是u,切断它的代价是c(1≤c≤100000)。 注意:两个中转站之间可能有多条道路直接相连。 同一行相邻两数之间可能有一个或多个空格。
对每条单向边，按输入顺序，依次输出一行，包含两个非0即1的整数，分 别表示对问题一和问题二的回答(其中输出1表示是，输出0表示否)。 同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。
题解：网络流+强连通分量
步骤：
1、先跑一波网络流求出残余网络（注意残余网络的边有可能比原图的边还要多）
2、对于残余网络，Trajan处理出scc[]，其中属于同一强连通分量的两个点scc[]值相等
3、判定：首先显然scc[s]!=scc[t]，那么有
①对于任意一条满流边(u,v)，(u,v)能够出现在某个最小割集中，当且仅当scc[u]!=scc[v]（在残余网络中，当然不存在边(u,v)，相反一定存在边(v,u)）
证明：将原图中（注意是原图所以这里不能dfs）每个强连通分量缩成一个点，得到的新图就只含有满流边了，而每一个这样的满流边都是最小割
②对于任意一条满流边(u,v)，(u,v)必定出现在最小割集中，当且仅当id[u]==id[S]且id[v]==id[T]
证明：假设将(u,v)的边权增大，那么残余网络中会出现S->u->v->T的通路，从而能继续增广，这也说明原图S和T就连通了
#include<stdio.h> #include<stack> #include<string.h> #include<queue> using namespace std; #define inf 2147483647 typedef struct { int x; int y; }Res; Res s[200005]; typedef struct { int to, next; int flow; }Road; Road G[200005]; stack<int> st; queue<int> q; int cnt, n, m, S, T, t, head[4010], h[4010], low[4010], time[4010], scc[4010]; void Add(int u, int v, int flow) { cnt++; G[cnt].next = head[u]; head[u] = cnt; G[cnt].to = v; G[cnt].flow = flow; } int Jud() { int now, i; queue<int> q; memset(h, -1, sizeof(h)); q.push(S); h[S] = 0; while(q.empty()==0) { now = q.front(); q.pop(); for(i=head[now];i!=0;i=G[i].next) { if(G[i].flow && h[G[i].to]==-1) { h[G[i].to] = h[now]+1; q.push(G[i].to); } } } if(h[T]!=-1) return 1; return 0; } int Sech(int x, int flow) { int w, used, i; if(x==T) return flow; used = 0; for(i=head[x];i!=0;i=G[i].next) { if(h[G[i].to]==h[x]+1) { w = Sech(G[i].to, min(flow-used, G[i].flow)); G[i].flow -= w; G[i^1].flow += w; used += w; if(used==flow) return flow; } } if(used==0) h[x] = -1; return used; } void Dinic() { while(Jud()) Sech(S, inf); } void Tarjan(int u) { int i, v; st.push(u); low[u] = time[u] = ++t; for(i=head[u];i!=0;i=G[i].next) { v = G[i].to; if(G[i].flow==0) continue; if(time[v]==0) { Tarjan(v); low[u] = min(low[u], low[v]); } else if(scc[v]==0) low[u] = min(low[u], time[v]); } if(low[u]==time[u]) { ++cnt; while(st.empty()==0) { v = st.top(); st.pop(); scc[v] = cnt; if(v==u) break; } } } int main(void) { int w, i, u, v; cnt = 1; scanf("%d%d%d%d", &n, &m, &S, &T); for(i=1;i<=m;i++) { scanf("%d%d%d", &s[i].x, &s[i].y, &w); Add(s[i].x, s[i].y, w); Add(s[i].y, s[i].x, 0); } Dinic(); cnt = 0; for(i=1;i<=n;i++) { if(time[i]==0) Tarjan(i); } for(i=1;i<=m;i++) { u = s[i].x, v = s[i].y; if(G[i*2].flow || scc[u]==scc[v]) printf("0 0\n"); else if(scc[u]==scc[S] && scc[v]==scc[T]) printf("1 1\n"); else printf("1 0\n"); } return 0; }
