歡迎來到網絡流（Network Flows）的世界！
你有沒有想過，城市在繁忙時間是如何疏導交通的？或者水是如何透過錯綜複雜的管道網絡，輸送到家家戶戶的？這正是網絡流所探討的課題！在本章中，我們將學習如何為這些現實世界的系統建立模型，從而找出「物件」（如汽車、水或數據）從起點到終點所能通過的最大流量。別擔心，這聽起來很複雜，我們會一步步為你拆解。
1. 基礎概念（DC1）
在開始計算之前，我們需要先掌握網絡的術語。想像一系列連接不同路口的單向街道。
關鍵術語：
- 源點（Source, S）：這是流量的起點。可以把它想像成水塔或工廠。
- 匯點（Sink, T）：這是流量的終點。可以把它想像成廚房水龍頭或倉庫。
- 節點（Nodes）：路徑相交的路口或點。
- 弧（Arcs）：連接節點的「管道」或「道路」。它們是有向（directed）的，意味著箭頭顯示了流量的方向。
- 容量（Capacity）：一條弧所能承載的最大流量。它通常寫在弧的旁邊。例如，一條容量為 \(5\) 的管道每秒最多可運送 \(5\) 公升的水。
- 流量（Flow）：當前流經該弧的實際數量。流量絕不能超過容量！
黃金法則：流量守恆（Conservation of Flow）
在任何網絡中，流入一個節點的量必須等於流出的量（源點和匯點除外）。如果 \(10\) 公升的水進入一個路口，就必須有 \(10\) 公升的水流出。水是不會憑空消失的！
快速回顧：一條標註為 \(3/5\) 的弧，表示容量為 \(5\)，但目前的流量只有 \(3\)。
重點總結：
網絡流問題本質上是一個謎題，我們嘗試在不超過弧的容量限制下，將盡可能多的「物體」從源點推送到匯點。
2. 進行「割」（Making the "Cut"）（DC2）
割（Cut）是一種將源點與匯點分離的方法。想像你拿著一把剪刀，切斷了某些弧，使得從 \(S\) 到 \(T\) 之間再也沒有路徑可言。
如何計算割的容量（Value of a Cut）
割的容量（Value）等於該割所切斷的所有弧的容量之和，但僅限於從源點一側指向匯點一側的弧。
逐步過程：
- 畫一條線，將源點一側與匯點一側完全分開。
- 找出這條線切斷的所有弧。
- 觀察箭頭的方向：
- 如果箭頭從源點一側指向匯點一側，則將其容量加入總和。
- 如果箭頭指向「反方向」（從匯點一側回到源點一側），則忽略它（它對該割的容量貢獻為 \(0\)）。
常見錯誤：學生經常把切線碰到的每一條弧都加起來。請記住：只計算那些從 \(S\) 側到 \(T\) 側「向前」的弧！
重點總結：
一個割告訴我們在網絡特定邊界上的最大潛在「通過量」。如果我們知道某個割的容量是 \(20\)，那麼我們可以肯定總流量絕不會超過 \(20\)。
3. 最大流最小割定理（Max-Flow Min-Cut Theorem）（DC3）
這聽起來很深奧，但它是數學中最優美的「捷徑」之一，也就是終極的「瓶頸法則」。
定理內容：網絡中的最大流（Maximum Flow）等於最小割（Minimum Cut）的容量。
為什麼會這樣？
想像一個漏斗。你可以往頂部倒多少水都行，但底部流出的水流大小取決於最窄的部分（瓶頸）。在網絡中，最小割就是那個瓶頸。它代表了整個系統中最嚴格的限制。
你知道嗎？
這個定理在冷戰時期曾被用於分析鐵路網絡！如果你想知道一個網絡能承受的最大流量，你只需要找出將其切開的「成本最低」（最小）的方法即可。
重點總結：
如果題目要求最大流，請試著找出你能找到的最小割容量。那個數字就是你的答案！
4. 超級源點與超級匯點（Supersources and Supersinks）（DC4）
有時候，生活並不如想像中簡單。你可能會遇到一個網絡包含三個不同的工廠（源點）和兩個不同的倉庫（匯點）。這看起來很亂，但我們有一個技巧可以解決它。
如何簡化網絡：
- 超級源點（Supersource）：建立一個名為「超級源點」的新節點。從這個超級源點畫一條有向弧指向每一個原始的源點。這些新弧的容量應為每個原始源點所能生產的總量。
- 超級匯點（Supersink）：建立一個名為「超級匯點」的新節點。從每個原始的匯點畫一條有向弧指向這個新的超級匯點。這些新弧的容量應為每個原始匯點所能接收的最大量。
類比：想像有三條小溪匯入一個湖泊。如果你想測量總水量，將其想像成一條巨大的「超級管道」同時供應三條小溪會容易得多！
如果起初覺得困惑也不要緊……只要記住這些「超級」節點只是「虛構」的點，我們用它們將複雜問題轉化為標準的單起點、單終點問題。
重點總結：
超級源點和超級匯點是「虛擬」節點，讓我們能對擁有多個起點或終點的網絡使用標準的最大流規則。
章節摘要與小貼士
- 流量 \( \le \) 容量：你無法將一加侖的水塞進一品脫的管道裡！
- 守恆：對於所有中間節點，流入流量 = 流出流量。
- 割的容量：只計算「向前」弧（\(S \to T\)）的容量總和。
- 最大流 = 最小割：瓶頸決定了流量上限。
- 多個起點/終點？使用超級源點或超級匯點將它們連接起來。