题目描述
给定一张图，对于每一条边询问：(1)是否存在割断该边的s-t最小割 (2)是否所有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表示否)。 同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。
样例输入
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 0 1 0 0 0 1 0 0 0 1 0 1 0
题解
网络流最小割+Tarjan
（貌似是某结论题？）
跑网络流最小割，然后在残量网络上跑Tarjan，缩点。
对于一条边满流的边x->y：
如果x与y所属的SCC不同，则该边可能出现在最小割上；
如果x与s所属的SCC相同且y与t所属的SCC相同，则该边一定出现在最小割上。
具体证明可以参考 （既然是结论题就懒得证结论了233）
#include#include #include #define N 4010#define M 120010using namespace std;queue q;typedef long long ll;int head[N] , to[M] , id[M] , next[M] , cnt = 1 , s , t , dis[N] , deep[N] , low[N] , tot , vis[N] , ins[N] , sta[N] , top , bl[N] , num , ans[M >> 1];ll val[M];inline void add(int x , int y , ll z , int i){ to[++cnt] = y , val[cnt] = z , id[cnt] = i , next[cnt] = head[x] , head[x] = cnt; to[++cnt] = x , val[cnt] = 0 , id[cnt] = 0 , next[cnt] = head[y] , head[y] = cnt;}bool bfs(){ int x , i; memset(dis , 0 , sizeof(dis)); while(!q.empty()) q.pop(); dis[s] = 1 , q.push(s); while(!q.empty()) { x = q.front() , q.pop(); for(i = head[x] ; i ; i = next[i]) { if(val[i] && !dis[to[i]]) { dis[to[i]] = dis[x] + 1; if(to[i] == t) return 1; q.push(to[i]); } } } return 0;}ll dinic(int x , ll low){ if(x == t) return low; ll temp = low , k; int i; for(i = head[x] ; i ; i = next[i]) { if(val[i] && dis[to[i]] == dis[x] + 1) { k = dinic(to[i] , min(temp , val[i])); if(!k) dis[to[i]] = 0; val[i] -= k , val[i ^ 1] += k; if(!(temp -= k)) break; } } return low - temp;}void tarjan(int x){ int i; deep[x] = low[x] = ++tot , vis[x] = ins[x] = 1 , sta[++top] = x; for(i = head[x] ; i ; i = next[i]) { if(val[i]) { if(!vis[to[i]]) tarjan(to[i]) , low[x] = min(low[x] , low[to[i]]); else if(ins[to[i]]) low[x] = min(low[x] , deep[to[i]]); } } if(deep[x] == low[x]) { int t; num ++ ; do { t = sta[top -- ]; bl[t] = num , ins[t] = 0; }while(t != x); }}int main(){ int n , m , i , x , y; ll z; scanf("%d%d%d%d" , &n , &m , &s , &t); for(i = 1 ; i <= m ; i ++ ) scanf("%d%d%lld" , &x , &y , &z) , add(x , y , z , i); while(bfs()) dinic(s , 1ll << 62); for(i = 1 ; i <= n ; i ++ ) if(!vis[i]) tarjan(i); for(x = 1 ; x <= n ; x ++ ) for(i = head[x] ; i ; i = next[i]) if(id[i] && !val[i]) ans[id[i]] = (bl[x] != bl[to[i]]) + ((bl[x] == bl[s] && bl[to[i]] == bl[t]) << 1); for(i = 1 ; i <= m ; i ++ ) printf("%d %d\n" , ans[i] & 1 , ans[i] >> 1); return 0;}