最大流與二分圖配對 (Max Flow & Bipartite Matching)#

很多看似毫不相干的問題——物流調度、頻寬分配、相親配對、廣告投放——背後其實是同一個模型：網路最大流。把它學透，等於一次解決了一整批問題。

問題：網路最大流#

把一張有向圖想成水管網路：每條邊有一個容量上限 (capacity)，水只能順著管子流，流經每條邊的量不能超過它的容量；除了源點與匯點之外，每個節點「流進來的量」必須等於「流出去的量」（水不會憑空產生或消失）。

問題是：從源點 S (source) 到匯點 T (sink)，最多能送多少流量？

flowchart LR
    S((S)) -->|10| A((A))
    S -->|8| B((B))
    A -->|5| B
    A -->|8| T((T))
    B -->|10| T((T))

這個抽象在現實中無處不在：

  • 物流網路：工廠是 S、賣場是 T，每條運輸線有車隊運能上限，問一天最多能送多少貨。
  • 網路頻寬：資料中心是 S、使用者是 T，每條鏈路有頻寬上限，問端到端最多能傳多少資料。
  • 供水/輸電：管線或電網的容量限制下，從源頭最多能送多少到終端。

最大流的關鍵不在「某一條路徑能送多少」，而在「整個網路協同起來能送多少」——不同路徑會共用邊、互相搶容量，必須整體看待。

最大流 - 最小割定理#

要理解最大流的上限從哪來，得先認識「割」。

什麼是割 (cut)#

把所有節點切成兩堆：一堆含 S，另一堆含 T。被切斷的、從 S 側指向 T 側的那些邊，它們的容量總和就是這個割的容量。

計算割容量時，只算 S 側 ➡️ T 側方向的邊。反方向（T 側 ➡️ S 側）的邊不計入。

以上圖為例，若把 {S, A} 分成 S 側、{B, T} 分成 T 側，被切斷且方向正確的邊是 S→B (8) 與 A→B (5) 與 A→T (8)，這個割的容量是 $8 + 5 + 8 = 21$。換一種切法可能得到更小的數字。

核心定理#

最大流 = 最小割容量（Max-Flow Min-Cut Theorem）。整個網路所能輸送的最大流量，恰好等於所有切法之中、容量最小的那一道割。

直覺很好懂：任何一道割，都是水流從 S 到 T 必經的一道「閘門」，流量不可能超過這道閘門的總容量。所以每一道割都是流量的上界，而最緊的那道上界（最小割）就是真正的瓶頸。定理告訴我們：這個瓶頸不只是上界，還一定能被達到。

$$ \max_{\text{flow}} ; |f| ;=; \min_{\text{cut}} ; c(S\text{-side}, T\text{-side}) $$

這也解釋了一個工程直覺：想擴大吞吐量，砸錢升級非瓶頸的邊毫無意義，只有拓寬最小割上的邊才有用。找到最小割，就找到了該投資的地方。

Ford-Fulkerson 演算法#

既然要求最大流，最自然的想法是：能多送就多送。

增廣路徑的直覺#

從零流量開始，反覆做一件事：在網路中找一條從 S 到 T、沿途每條邊都還有剩餘容量的路徑，這叫增廣路徑 (augmenting path)。沿這條路徑灌入「路徑上最小剩餘容量」那麼多的流量。重複，直到再也找不到任何增廣路徑為止——此時的流量就是最大流。

flowchart TD
    A[流量歸零] --> B{在殘餘網路中<br/>找得到 S→T 路徑?}
    B -->|是| C[沿路徑灌入<br/>瓶頸容量的流量]
    C --> D[更新殘餘網路]
    D --> B
    B -->|否| E[當前流量即最大流]

    style E fill:#e8f5e9

殘餘網路與「反悔」#

天真地貪心會踩到一個坑：早期某條路徑的選擇，可能堵死了後面更好的安排。Ford-Fulkerson 用殘餘網路 (residual network) 解決這個問題。

每條原始邊 u→v 灌了流量 $f$ 之後，殘餘網路裡會有：

  • 正向殘餘邊 u→v，剩餘容量 = 容量 $-,f$，代表「還能再多送多少」。
  • 反向殘餘邊 v→u，容量 = $f$，代表「之前送過去的，可以抽回來多少」。

反向邊是整個演算法的精髓：它讓後續的增廣路徑能夠沿反向邊「退掉」一部分先前的流量分配，把容量讓給更好的走法。等於給了演算法「反悔」的能力，這正是貪心地灌流量卻仍能保證全域最優的原因。

只要殘餘網路中還存在一條 S➡️T 的路徑，就代表還有改進空間；找不到了，當前 S 可達的節點集合恰好定義出一個最小割——這正是最大流 - 最小割定理在演算法層面的體現。

Edmonds-Karp 改進版#

Ford-Fulkerson 沒規定「怎麼找」增廣路徑。如果每次都用 BFS 找邊數最少的最短增廣路徑，就得到 Edmonds-Karp 演算法，複雜度為 O(V·E²)——與容量數值大小無關，這在容量很大時尤其重要（單純的 DFS 找法在極端情況下可能很慢）。

Edmonds-Karp 程式碼
fun edmondsKarp(capacity: Array<IntArray>, s: Int, t: Int): Int {
    val n = capacity.size
    var flow = 0

    while (true) {
        // BFS 在殘餘網路中找最短增廣路徑
        val parent = IntArray(n) { -1 }
        parent[s] = s
        val queue = ArrayDeque<Int>()
        queue.add(s)

        bfs@ while (queue.isNotEmpty()) {
            val u = queue.removeFirst()
            for (v in 0 until n) {
                if (parent[v] == -1 && capacity[u][v] > 0) {
                    parent[v] = u
                    if (v == t) break@bfs
                    queue.add(v)
                }
            }
        }

        if (parent[t] == -1) break  // 找不到增廣路徑

        // 找出路徑上的瓶頸容量
        var bottleneck = Int.MAX_VALUE
        var v = t
        while (v != s) {
            val u = parent[v]
            bottleneck = minOf(bottleneck, capacity[u][v])
            v = u
        }

        // 沿路徑更新殘餘網路（正向減、反向加）
        v = t
        while (v != s) {
            val u = parent[v]
            capacity[u][v] -= bottleneck
            capacity[v][u] += bottleneck
            v = u
        }

        flow += bottleneck
    }

    return flow
}

二分圖最大配對 ≡ 最大流#

最大流真正展現威力的地方，是它能解掉一個乍看完全不同的問題：二分圖最大配對。

什麼是二分圖配對#

二分圖 (bipartite graph)：節點分成左右兩組，邊只連在兩組之間、組內沒有邊。最大配對 (maximum matching) 就是：在「一個點最多只配一個」的限制下，最多能配成幾對。

flowchart LR
    subgraph 左組
        L1((司機1))
        L2((司機2))
        L3((司機3))
    end
    subgraph 右組
        R1((乘客A))
        R2((乘客B))
        R3((乘客C))
    end
    L1 --- R1
    L1 --- R2
    L2 --- R2
    L3 --- R3

建模技巧：化配對為流量#

如何把配對問題變成最大流？只要動三個小手腳：

  1. 加一個源點 S，連到左組每一個點。
  2. 加一個匯點 T，右組每一個點都連到 T。
  3. 所有邊（含 S、T 那些）容量都設為 1，方向都是 S ➡️ 左 ➡️ 右 ➡️ T。

在這張圖上跑一次最大流，得到的最大流量值就是最大配對數。

為什麼成立？容量為 1 的限制保證了「一對一」：每個左點最多有 1 單位流量流入（所以最多配一個右點），每個右點最多流出 1 單位（所以最多被一個左點配走）。每送出 1 單位流量，對應一條 S➡️ 左 ➡️ 右 ➡️T 的路徑，也就對應一組成功的配對。

flowchart LR
    S((S)) -->|1| L1((司機1))
    S -->|1| L2((司機2))
    L1 -->|1| R1((乘客A))
    L1 -->|1| R2((乘客B))
    L2 -->|1| R2
    R1 -->|1| T((T))
    R2 -->|1| T((T))

真實應用#

左組右組配對的意義
司機乘客派遣系統把可服務的司機配給乘客
讀者推薦內容在偏好/容量限制下分配推薦項目
關鍵字廣告競價系統把廣告位配給合適的廣告
求職者職缺在資格符合下安排最多的錄取對

這些問題的表面措辭天差地別，但「左右兩組、在容量限制下求最多一對一」的骨架完全相同。能從一個具體場景中看出它其實是配對問題、再進一步看出配對就是最大流，正是演算法思維總綱所說的「把陌生問題抽象成已知模型」這項最高層次能力的具體體現。

小結#

概念一句話
網路最大流容量限制下，S 到 T 能送的最大流量
最小割把網路一分為二的最窄瓶頸
最大流 - 最小割定理最大流量 = 最小割容量
增廣路徑殘餘網路中還能加流量的 S➡️T 路徑
反向邊賦予演算法「反悔」能力，保證全域最優
Edmonds-Karp用 BFS 找最短增廣路徑，O(V·E²)
二分圖配對加 S、T、容量設 1，跑最大流即得最大配對

最大流的價值，一半在演算法本身，一半在它示範了「不同問題等價」的威力。下次遇到「在限制下做最多分配」的問題時，先問一句：這會不會也是一個最大流？

Backward 最短路徑 PageRank：圖上的隨機遊走 Forward