s-t 最小割

最小割问题可以形象地理解为：为了不让水从 s 流向 t，怎么破坏水沟代价最小？被破坏的水沟必然是从 s 到 t 的单向水沟。而在有向图流网络 G = (V，E) 中，割把图分成 S 和 T = V - S 两部分，源点 s ∈ S，汇点 t ∈ T，这称为 s - t 割。
最大流最小割定理：源点 s 和 汇点 t 之间的最小割等于 s 和 t 之间的最大流。
需要注意的是，定理中的最大流是指流量，而最小割是指容量。
全局最小割：把 s-t 最小割问题扩展到全局，有全局最小割问题。

问题一，是否存在一个最小割，其中该边被割？

对于一条边的两个端点 u， v，若该边存在一个最小割中，则在最大流的残留网络中一定不存在一条从 u 到 v 的增广路，否则说明不是最小割。所以我们对最大流的残留网络中的强连通分量进行缩点，缩点后图中剩余的边就只剩下两种边了，一种是残留网络中由 t 到 s 建的的反边，另一种是无法连接 s 和 t 的无用边，而这两种边是很好区分的，第一种边的流量等于它的容量也就是满流，而另一种边是没有流量的也就是零流。

问题二，是否对任何一个最小割，都有该边被割？

在问题一的基础上，把强连通分量缩点后，只用一条就能连接缩点 s 和缩点 t 的边就是对于任何一个最小割，都有该边被割。

// 牛客 （https://ac.nowcoder.com/acm/problem/19887）
#include<bits/stdc++.h>

using namespace std;

const int maxn = 4001;
const int maxm = 60001;

struct edge{
    int to, next, cap, flow, f1, f2;
}e[maxm << 1]; int head[maxn], tot;
int n, m, s, t, d[maxn];
int dfn[maxn], low[maxn], cnt;
int scc[maxn], sta[maxn], coc, top;

void addedge(int u, int v, int w) {
    e[++tot] = {v, head[u], w, 0, 0, 0}, head[u] = tot;
    e[++tot] = {u, head[v], 0, 0, 0, 0}, head[v] = tot;
}

void init() {
    memset(head, -1, sizeof head), tot = -1;
}

bool bfs() {
    memset(d, 0x7f, sizeof d);
    queue<int> q; q.push(t);
    d[t] = 0;
    while(!q.empty()) {
        int x = q.front(); q.pop();
        for(int i = head[x]; ~i; i = e[i].next) {
            int j = e[i].to;
            if (d[j] > d[x] + 1 && e[i^1].cap > e[i^1].flow) {
                d[j] = d[x] + 1;
                q.push(j);
            }
        }
    }
    return d[s] != d[0];
}

int dfs(int x, int flow, int used = 0) {
    if (x == t) return flow;
    for(int i = head[x]; ~i && flow != used; i = e[i].next) {
        int j = e[i].to, f;
        if (d[x] - 1 == d[j] && e[i].cap > e[i].flow) {
            f = dfs(j, min(flow - used, e[i].cap - e[i].flow));
            if (f) e[i].flow += f, e[i^1].flow -= f, used += f;
        }
    }
    if (!used) d[x] = 0;
    return used;
}

void DFS(int x) {
    dfn[x] = low[x] = ++ cnt;
    sta[top++] = x;
    for(int i = head[x]; ~i; i = e[i].next) {
        int j = e[i].to;
        if (e[i].cap > e[i].flow)
        if (!dfn[j]) {
            DFS(j);
            low[x] = min(low[j], low[x]);
        }
        else if (!scc[j]) {
            low[x] = min(dfn[j], low[x]);
        }
    }
    if (dfn[x] == low[x]) {
        ++ coc;
        while(1) {
            int y = sta[--top];
            scc[y] = coc;
            if (y == x) break;
        }
    }
}

void tarjin(int n) {
    coc = top = cnt = 0;
    for(int i = 1; i <= n; ++ i) {
        scc[i] = low[i] = dfn[i] = 0;
    }
    for(int i = 1; i <= n; ++ i)
        if (!scc[i]) DFS(i);
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    init();
    for(int i = 1; i <= m; ++ i) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        addedge(u, v, w);
    }
    while(bfs()) dfs(s, INT_MAX);
    tarjin(n);
    for(int i = 0; i <= tot; i += 2) {
        int u = e[i^1].to, v = e[i].to;
        if (e[i].flow && scc[u] != scc[v])
            e[i].f1 = 1;
        if (scc[u] == scc[s] && scc[v] == scc[t])
            e[i].f2 = 1;
    }
    for(int i = 0; i <= tot; i += 2) {
        printf("%d %d\n", e[i].f1, e[i].f2);
    }
    return 0;
}