最小割等於最大流——這個定理讓「找瓶頸」和「找最大輸送量」是同一個問題。
問題的本質
一個管道網路，每條管道有容量限制。從水源 s 到終點 t，最多能送多少水？
暴力找路徑送水——找到一條 s→t 的路徑，沿這條路盡量送水。問題是貪婪選路可能堵死後面更好的方案。
殘餘圖（Residual Graph） 是解法的核心：
對容量 c、已流量 f 的邊 (u→v)：
正向邊：剩餘容量 = c - f（還能送多少）
反向邊：容量 = f（允許「退回」之前送出的流量）反向邊的意義是讓演算法能撤銷錯誤的選擇——等同於「取消這條路上的流，改送其他路徑」。有了殘餘圖，每次找到增廣路徑後更新，直到找不到為止。
Edmonds-Karp：BFS 增廣
Ford-Fulkerson 框架加上 BFS（確保每次找最短增廣路）：
int edmondsKarp(int s, int t) {
int maxFlow = 0;
while (true) {
int[] parent = bfs(s, t); // BFS 找增廣路徑
if (parent[t] == -1) break;
int flow = Integer.MAX_VALUE;
for (int v = t; v != s; v = parent[v])
flow = Math.min(flow, residual(parent[v], v));
for (int v = t; v != s; v = parent[v]) {
reduce(parent[v], v, flow); // 正向邊減少剩餘容量
increase(v, parent[v], flow); // 反向邊增加剩餘容量
}
maxFlow += flow;
}
return maxFlow;
}時間複雜度：O(VE²)。
🎬 互動視覺化：Edmonds-Karp 最大流 — 一步步看 BFS 找增廣路、沿路取瓶頸容量、正反向邊同步更新殘餘圖，直到 s 再也走不到 t。反向邊「退流」那一刻特別值得盯著看。
Dinic：分層圖 + 阻塞流
競程標準選擇，比 Edmonds-Karp 快很多：
兩步驟反覆執行到 t 不可達：
1. BFS 建分層圖（把節點按離 s 的 BFS 距離分層）
2. DFS 在分層圖中找阻塞流（一次 DFS 推進多條增廣路）
時間複雜度：O(V² E)
單位容量圖（競程常見）：O(E √V)Dinic 快的原因：每輪 BFS 後做完整的阻塞流，一次推進多條路徑，不像 Edmonds-Karp 每輪只推一條。
實作上多兩個小地方要顧——分層用 BFS 標高度，DFS 推流時用「當前弧」指標 iter[] 記住每個節點試到第幾條邊，避免同一輪反覆撞已經榨乾的邊：
int dinic(int s, int t) {
int maxFlow = 0;
while (bfsLevel(s, t)) { // 建分層圖，t 不可達就收工
int[] iter = new int[V]; // 當前弧：跳過本輪已飽和的邊
int f;
while ((f = dfsBlock(s, t, INF, iter)) > 0)
maxFlow += f; // 榨完這層的阻塞流
}
return maxFlow;
}實務上你幾乎不用糾結該挑哪個——一般題目 Edmonds-Karp 就夠，會 TLE 或跑二分圖匹配才換 Dinic：
| 演算法 | 時間複雜度 | 什麼時候用它 |
|---|---|---|
| Ford-Fulkerson | O(maxFlow × E) | 容量是整數、流量本身很小 |
| Edmonds-Karp | O(VE²) | 一般用途的安全牌 |
| Dinic | O(V²E) | 競程標準，Edmonds-Karp 會 TLE 時改用它 |
| Dinic（單位容量） | O(E√V) | 二分圖匹配這種每條邊容量都是 1 的圖 |
最大二分圖匹配
工作分配問題：m 個工人、n 個工作，每個工人能做某些工作，最多能成功分配幾對？
建圖：
超級源點 s → 每個工人（容量 1）
每個工作 → 超級匯點 t（容量 1）
工人 i → 工作 j（若 i 能做 j，容量 1）
最大流 = 最大匹配數
為什麼：每個工人最多被選一次（容量 1），每個工作最多被分配一次（容量 1）最大流 = 最小割
最大流最小割定理：圖中從 s 到 t 的最大流 = 將 s 和 t 分開所需移除的最小邊容量總和。
最小割回答「哪裡是瓶頸」——供應鏈分析（哪條路徑最容易中斷）、網路安全（切斷哪些連接能隔離攻擊）。
殘餘圖的反向邊是個反直覺的設計——它讓演算法有能力承認錯誤並改正，這才是為什麼最大流能找到全局最優解。
接下來往哪走
- Rolling Hash 滾動雜湊：O(1) 的子字串比較 — 下一篇：從圖論切到字串，競程的另一個基本功
- Advanced Graph 進階圖論 — 二分圖匹配的匈牙利演算法版本、SCC、割點橋都在這裡
- Graph Algorithms 圖演算法（上）：最短路徑 — Edmonds-Karp 和 Dinic 都建立在 BFS 之上，基礎在這裡