第 31 章 進階 約 18 分鐘
網路流：水管最多能流多少水？
從水庫到城市，中間有很多水管各有容量上限。每秒最多能送多少水？這是 Max-Flow 問題。
建議先看過： 13-bfs-dfs
問題場景
從水源 s（source）送水到匯流 t（sink）。中間有多條水管，每條有容量上限。 問：每秒最多能送多少水從 s 到 t？
延伸應用：
- 網路頻寬規劃
- 物流配送
- 二分圖匹配（員工配工作、男生配舞伴）
- 影像分割（電腦視覺）
Ford-Fulkerson：找擴充路徑
核心想法：從 s 到 t 找任何一條「還有剩餘容量」的路徑，沿路加流量到容量瓶頸值，重複直到找不到為止。
每次找到的這種路徑叫 擴充路徑 (augmenting path)。
跑一遍：
Step 1: 找路徑 s→a→c→t，瓶頸=10。流量+10
Step 2: 找路徑 s→b→d→t，瓶頸=10。流量+10
Step 3: 找路徑 s→a→...？沒了，s→a 已滿
→ 總流量 = 20核心概念：殘餘圖（Residual Graph）
每條邊有兩個容量：
- 正向：剩餘 = 容量 - 已用
- 反向：剩餘 = 已用流量（讓你「反悔」）
反向邊是關鍵——允許之前的決策被撤銷，否則貪婪選錯就回不去。
Pseudocode
Algorithm FordFulkerson(graph, s, t):
flow ← 0
while 存在 s→t 的擴充路徑 P (殘餘圖中) :
bottleneck ← P 上的最小殘餘容量
for (u, v) in P:
residual[u][v] ← residual[u][v] - bottleneck
residual[v][u] ← residual[v][u] + bottleneck // 反向加
flow ← flow + bottleneck
return flow
找擴充路徑用什麼？
- DFS：可能找超長路徑，時間 O(E × max_flow)，最壞會跑很久
- BFS：找最短路徑 → 演算法叫 Edmonds-Karp，時間 O(V × E²)——比較保險
Max-Flow Min-Cut 定理
最大流 = 最小割。
割 (cut) = 把點分成兩半（s 一邊、t 一邊）後，跨越兩半的邊的容量總和。 最小割 = 容量總和最小的那個割。
這個定理超優雅——告訴你「到底是哪些邊在限制流量」。
💡二分圖匹配 = 網路流的小弟
左邊 N 個男生、右邊 M 個女生，誰跟誰能配對是邊。問最多能配幾對？
把它變成網路流：
- 加超級源點 s 連所有男生（容量 1）
- 加超級匯點 t 給所有女生連（容量 1）
- 原本的男女連線容量設 1
- 跑 max flow
Max flow = 最大匹配數。
複雜度
| 演算法 | 時間 |
|---|---|
| Ford-Fulkerson (DFS) | O(E × max_flow) |
| Edmonds-Karp (BFS) | O(V × E²) |
| Dinic’s | O(V² × E) |
實務上：Edmonds-Karp 簡單可靠，Dinic’s 更快但難實作。
📝考試會這樣考
題型一：跑一遍 Ford-Fulkerson。 給網路圖，列出每次找的擴充路徑、瓶頸、累計流量。
題型二：找最小割。 跑完 max flow 後，從 s 用 BFS 在殘餘圖走，能走到的點集合為 S，剩下的為 T。割邊 = S 到 T 的原圖邊。
題型三：為什麼需要反向邊？ 答：允許「撤銷錯誤決策」。沒有反向邊，貪婪選錯就回不去，得不到最大流。
題型四：二分圖匹配怎麼建圖？ 答：加超級源點+匯點，所有邊容量=1，跑 max flow。
題型五：Max-Flow Min-Cut 定理。 死背：最大流量 = 最小割容量。
這章記住
- Ford-Fulkerson 找擴充路徑，反覆增加流量。
- 反向邊允許撤銷，是演算法正確性的關鍵。
- Edmonds-Karp = Ford-Fulkerson + BFS，O(V × E²)。
- Max-Flow = Min-Cut——這個定理會考。
- 應用：頻寬、物流、二分圖匹配、影像分割。
學習進度只存在你的瀏覽器，不會上傳。