最小割等於最大流——這個定理讓「找瓶頸」和「找最大輸送量」是同一個問題。
問題的本質
一個管道網路，每條管道有容量限制。從水源 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²)。
Dinic：分層圖 + 阻塞流
競程標準選擇，比 Edmonds-Karp 快很多：
兩步驟反覆執行到 t 不可達：
1. BFS 建分層圖（把節點按離 s 的 BFS 距離分層）
2. DFS 在分層圖中找阻塞流（一次 DFS 推進多條增廣路）
時間複雜度：O(V² E)
單位容量圖（競程常見）：O(E √V)
Dinic 快的原因：每輪 BFS 後做完整的阻塞流，一次推進多條路徑，不像 Edmonds-Karp 每輪只推一條。
最大二分圖匹配
工作分配問題：m 個工人、n 個工作，每個工人能做某些工作，最多能成功分配幾對？
建圖：
超級源點 s → 每個工人（容量 1）
每個工作 → 超級匯點 t（容量 1）
工人 i → 工作 j（若 i 能做 j，容量 1）
最大流 = 最大匹配數
為什麼：每個工人最多被選一次（容量 1），每個工作最多被分配一次（容量 1）
最大流 = 最小割
最大流最小割定理：圖中從 s 到 t 的最大流 = 將 s 和 t 分開所需移除的最小邊容量總和。
最小割回答「哪裡是瓶頸」——供應鏈分析（哪條路徑最容易中斷）、網路安全（切斷哪些連接能隔離攻擊）。
殘餘圖的反向邊是個反直覺的設計——它讓演算法有能力承認錯誤並改正，這才是為什麼最大流能找到全局最優解。