🎯 什麼情境該想到我
當你「要在一個有容量限制的網路裡送最多的東西」的時候——頻寬、物流、管線。
★ 但它真正的價值在於大量看起來不像流的問題可以被轉化成流：二分圖匹配、排班、專案選擇、影像分割。
認出「這題其實是最大流」比會寫演算法更有價值。
⚙️ 怎麼用（機制與建模）
問題定義
有向圖，每條邊有容量 ，有源點 與匯點 。求 的最大流量，滿足：
- 容量限制：每條邊的流量 容量
- 流量守恆：除 、 外，每個點的流入 = 流出
★ 核心觀念：殘差圖與反向邊
直覺的貪婪做法會失敗：隨便找一條路填滿，可能擋住更好的方案。
解法：允許「反悔」。
殘差容量：
正向邊 (u,v)：c(u,v) - f(u,v) 還能再送多少
★ 反向邊 (v,u)：f(u,v) 已經送了多少 —— 可以「退回」
在殘差圖上找一條 s→t 的路（增廣路），
沿路加上該路徑的最小殘差容量。
沒有增廣路了 → 就是最大流。
★ 反向邊是整個演算法的靈魂。
它讓演算法可以「把先前送過的流量推回去，改走別條路」——
不需要真的回溯，貪婪就變成了正確的演算法。
這是一個很值得記住的算法設計技巧：把「反悔」編碼進資料結構裡。
★ 最大流最小割定理（這題的核心結論）
最大流的值 = 最小割的容量。
「割」= 把節點分成含 的 與含 的 ；
割的容量 = 所有從 指向 的邊的容量總和。
直覺：任何流都必須完整穿過每一個割，所以 流 任意割。
而演算法結束時（沒有增廣路），從 在殘差圖上可達的點集就構成一個割，
其容量恰等於當前流量 → 兩者相等。
實務意義（★ 比定理本身更有用）：
- 最大流告訴你「能送多少」
- 最小割告訴你「瓶頸是哪幾條邊」 ← 這才是你要拿去優化的
- 演算法跑完後，從 在殘差圖上做一次 廣度優先搜尋，可達的點就是 ，跨出去的邊就是瓶頸
演算法
| 演算法 | 找增廣路的方式 | 複雜度 |
|---|---|---|
| Ford-Fulkerson | 任意路徑（如 DFS） | —— ★ 依賴流量大小，無理數容量甚至不終止 |
| ★ Edmonds-Karp | 用 BFS 找「最短」增廣路 | —— 與流量無關 |
| Dinic | BFS 分層 + DFS 多路增廣 | ；單位容量圖上 ← 二分圖匹配就是這個 |
| ISAP / HLPP | 更複雜的優化 | 實務上競賽用 |
★ 實務上寫 Dinic。Edmonds-Karp 好懂好寫但慢，Dinic 只複雜一點卻快很多。
★ 建模才是重點：常見的轉化
| 問題 | 怎麼轉成流 |
|---|---|
| ★ 二分圖最大匹配 | 加超級源點 連所有左側點（容量 1）、所有右側點連超級匯點 （容量 1）、原有的邊容量 1。 最大流 = 最大匹配。Dinic 在此是 （= Hopcroft-Karp） |
| ★ 排班／任務指派 | 人 → 左側、時段/任務 → 右側，容量代表「一個人最多接幾個」 |
| 點也有容量 | 拆點：把 拆成 ，中間一條容量 = 點容量的邊 |
| 多源多匯 | 加超級源點與超級匯點 |
| 最小路徑覆蓋（DAG） | − 最大匹配 |
| 專案選擇 / 最大權閉合子圖 | 最小割模型：收益點連 、成本點連 、相依關係容量 ∞ |
| ★ 影像分割 | 像素當點，前景/背景當 /，最小割 = 最佳分割邊界（graph cut） |
★ 「拆點」和「加超級源匯」是建模的兩個萬用技巧，值得單獨記住。
複雜度的實務感覺
Dinic 在一般圖上的實測遠好於理論上界。但流問題的規模上限通常在數千個點、數萬條邊——
再大就要考慮近似或專用演算法（見 近似演算法）。
🧪 我實際套用的紀錄
- （待填）
⚠️ 注意 / 什麼時候不適用
- ★ Ford-Fulkerson 的複雜度依賴流量大小。容量是 的圖上可能跑到天荒地老（經典反例：兩條容量 的路中間夾一條容量 1 的邊，每次只增廣 1）。用 BFS 找最短增廣路（Edmonds-Karp）就解決了。
- ★ 反向邊一定要建。漏掉就不是最大流演算法了（會退化成錯誤的貪婪）。實作上常用「成對存邊，
i^1取得反向邊」的技巧。 - 最小割不唯一，但容量唯一。
- ★ 有「下界」的流（每條邊至少要送多少）是另一個問題（有源匯上下界可行流），要額外建模，不能直接套。
- 最小費用最大流是不同的問題，要用 SPFA/Dijkstra 找最短（費用）增廣路。
- 實務上先問「這真的是流問題嗎」。很多資源分配問題用貪婪或線性規劃更直接。流的價值在於「有整數解保證」（容量為整數時，最大流必有整數解——這是二分圖匹配能用它的原因）。
- 這是這批筆記裡最少用到的一個。除非做排程、匹配、或影像分割，否則實務上很少遇到。