分析

主要考察最小割的性质。我们发现如果一条边是可行边，那么一定要满足以下性质。

• 满流，没有第二条增广路 。考虑证明，如果没有满流，那么我们完全没必要割去这条边。如果有，那么证明这个路径还可以继续增广，不满足最小割的定义。
  那么如果一条边是必须边。

• 满流，直接链接 所在集合。这里考虑最小割的定义。

那么我们只需要通过 把 求出来就行了。数组开的很奔放，不用太在意。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 4e5 + 100,inf = 0x3f3f3f3f;
int read() {
    int x = 0;char ch = getchar();
    while(!isdigit(ch)) {ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return x;
}
struct Edge{int to,nxt,from,cap;}e[N<<1];
int head[N],dis[N],cur[N],dfn[N],low[N],scc[N],vis[N],st[N],top,ecnt = 1;
int n,m,S,T;
queue<int> Q;
bool Bfs(int s,int t) {
    memset(dis,0,sizeof(dis));dis[s] = 1;while(Q.size()) Q.pop();
    Q.push(s);
    while(!Q.empty()) {
        int x = Q.front();Q.pop();
        for(int i = head[x];i;i = e[i].nxt) {
            int y = e[i].to;if(!dis[y] && e[i].cap > 0) {
                dis[y] = dis[x] + 1;if(y == t) return true;
                Q.push(y);
            }
        }
    }
    return false;
}
int Dfs(int x,int a,int t) {
    if(x == t || a == 0) return a;
    int flow = 0,f = 0;
    for(int i = cur[x];i;i = e[i].nxt) {
        int y = e[i].to;cur[x] = i;
        if((dis[y] == dis[x] + 1) && ((f = Dfs(y,min(a,e[i].cap),t)) > 0)) {
            e[i].cap -= f;e[i^1].cap += f;flow += f;a -= f;if(!a) break;
        }
    }
    return flow;
}
void add(int x,int y,int cap) {
    e[++ecnt].to = y;e[ecnt].from = x;e[ecnt].cap = cap;e[ecnt].nxt = head[x];head[x] = ecnt;
    e[++ecnt].to = x;e[ecnt].from = 0;e[ecnt].cap = 0  ;e[ecnt].nxt = head[y];head[y] = ecnt;
}
int Scc,Tim;
void tarjan(int x) {
    dfn[x] = low[x] = ++Tim;vis[x] = 1;st[++top] = x;
    for(int i = head[x];i;i = e[i].nxt) {
        int y = e[i].to;if(!e[i].cap) continue;
        if(!dfn[y]) {
            tarjan(y);low[x] = min(low[x],low[y]);
        }
        else if(vis[y]) low[x] = min(low[x],dfn[y]);
    }
    if(dfn[x] == low[x]) {
        Scc++;scc[x] = Scc;
        while(st[top] != x) {
            scc[st[top]] = Scc;vis[st[top]] = 0;top--;
        }
        top--;vis[x] = 0;
    }

}
int main() {
    n = read();m = read();S = read();T = read();
    for(int i = 1;i <= m;i++) {
        int x = read(),y = read(),c = read();add(x,y,c);
    }
    int Maxflow = 0;
    while(Bfs(S,T)) {
        for(int i = 1;i <= n;i++) cur[i] = head[i];Maxflow += Dfs(S,inf,T);
    }
    for(int i = 1;i <= n;i++) {if(!dfn[i]) tarjan(i);}
    for(int i = 2;i <= ecnt;i += 2) {
        if(!e[i].cap) {
            printf("%d %d\n",(scc[e[i].from] != scc[e[i].to]),((scc[e[i].from] == scc[S]) && (scc[e[i].to] == scc[T])) );
        }
        else printf("0 0 \n");
    }
    return 0; 
}