P4126 [AHOI2009]最小割

题目地址：[P4126 [AHOI2009]最小割](https://www.luogu.org/problemnew/show/P4126) #### 最小割的可行边与必须边 首先求最大流，那么最小割的可行边与必须边都必须是**满流**。 * 可行边：在残量网络中不存在 $x$ 到 $y$ 的路径（强连通分量）； * 必须边：在残量网络中 $S$ 能到 $x$ && $y$ 能到 $T$ 。 ```cpp #include <bits/stdc++.h> using namespace std; const int N = 4e3 + 6, M = 6e4 + 6, inf = 1e9; int n, m, s, t, d[N], f[N]; int Head[N], Edge[M<<1], Leng[M<<1], Next[M<<1], tot = 1; struct E { int x, y, z; } e[M<<1]; int dfn[N], low[N], num, st[N], top, ins[N], c[N], cnt; inline void add(int x, int y, int z) { Edge[++tot] = y; Leng[tot] = z; Next[tot] = Head[x]; Head[x] = tot; } inline bool bfs() { memset(d, 0, sizeof(d)); queue<int> q; d[s] = 1; q.push(s); while (q.size()) { int x = q.front(); q.pop(); for (int i = Head[x]; i; i = Next[i]) { int y = Edge[i], z = Leng[i]; if (d[y] || !z) continue; d[y] = d[x] + 1; q.push(y); if (y == t) return 1; } } return 0; } int dinic(int x, int flow) { if (x == t) return flow; int rest = flow; for (int i = Head[x]; i && rest; i = Next[i]) { int y = Edge[i], z = Leng[i]; if (d[y] != d[x] + 1 || !z) continue; int k = dinic(y, min(z, rest)); if (!k) d[y] = 0; else { Leng[i] -= k; Leng[i^1] += k; rest -= k; } } return flow - rest; } void dfs(int x, int k) { f[x] = k; for (int i = Head[x]; i; i = Next[i]) { int y = Edge[i], z = Leng[i^(k-1)]; if (f[y] || !z) continue; dfs(y, k); } } void tarjan(int x) { dfn[x] = low[x] = ++num; st[++top] = x; ins[x] = 1; for (int i = Head[x]; i; i = Next[i]) { int y = Edge[i], z = Leng[i]; if (!z) continue; if (!dfn[y]) { tarjan(y); low[x] = min(low[x], low[y]); } else if (ins[y]) low[x] = min(low[x], dfn[y]); } if (dfn[x] == low[x]) { ++cnt; int y; do { y = st[top--]; ins[y] = 0; c[y] = cnt; } while (x != y); } } int main() { cin >> n >> m >> s >> t; for (int i = 1; i <= m; i++) { scanf("%d %d %d", &e[i].x, &e[i].y, &e[i].z); add(e[i].x, e[i].y, e[i].z); add(e[i].y, e[i].x, 0); } while (bfs()) while (dinic(s, inf)); dfs(s, 1); dfs(t, 2); for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i); for (int i = 1; i <= m; i++) { int k = i << 1; if (Leng[k]) puts("0 0"); else printf("%d %d\n", c[e[i].x] != c[e[i].y], f[e[i].x] == 1 && f[e[i].y] == 2); } return 0; } ```