cover.png#网络流

同样，网络流参考集合与图论笔记

流网络 (CLRS 26.1)

流网络是有向图 \(G = (V, E)\)，带有： - 源点 \(s\) 和汇点 \(t\) - 容量函数 \(c: V \times V \to \mathbb{R}_{\geq 0}\)，若 \((u,v) \notin E\) 则 \(c(u,v) = 0\)

约定：不允许自环；若 \((u,v) \in E\) 则 \((v,u) \notin E\)（可处理反平行边）；图连通，每个顶点至少在一条边上

流的定义

流 \(f: V \times V \to \mathbb{R}\) 满足：

1. 容量约束：\(0 \leq f(u,v) \leq c(u,v)\)，对所有 \(u, v \in V\)
2. 流量守恒：对所有 \(u \in V \setminus \{s, t\}\)，\(\sum_{v \in V} f(v, u) = \sum_{v \in V} f(u, v)\)

即：流入量 \(=\) 流出量（对非源非汇节点）

流的值：

\[|f| = \sum_{v \in V} f(s, v) - \sum_{v \in V} f(v, s)\]

即从源点的净流出量

目标：找最大流值

反平行边的处理

若原图中同时有 \((u,v)\) 和 \((v,u)\)，引入新节点 \(v'\)：

将 \((v,u)\) 替换为 \((v, v')\) 和 \((v', u)\)，容量相同

多源多汇

多个源 \(s_1, \ldots, s_p\) 和多个汇 \(t_1, \ldots, t_q\)

转化：添加超级源 \(S\) 和超级汇 \(T\)

• \(S \to s_i\) 容量 \(\infty\)
• \(t_j \to T\) 容量 \(\infty\)

转化后单源单汇最大流等于原问题最大流

隐式求和记号

\(f(X, Y) = \sum_{x \in X, y \in Y} f(x, y)\)

性质 (CLRS Lemma 26.1)：

1. \(f(X, X) = 0\)（反对称性的推广）
2. \(f(X, Y) = -f(Y, X)\)
3. \(f(X \cup Y, Z) = f(X, Z) + f(Y, Z)\)，若 \(X \cap Y = \emptyset\)
4. \(|f| = f(s, V) = f(V, t)\)

点击查看性质 4 证明

\[f(V, V) = 0\]

\[f(V, V) = f(V, s) + f(V, t) + f(V, V \setminus \{s,t\}) = 0\]

由流量守恒，\(f(V, u) = 0\) 对所有 \(u \in V \setminus \{s,t\}\)

\[f(V, V \setminus \{s,t\}) = \sum_{u \in V \setminus \{s,t\}} f(V, u) = 0\]

\[f(V, s) + f(V, t) = 0\]

\[f(V, t) = -f(V, s) = f(s, V) = |f|\]

---

残余网络 (CLRS 26.2)

残余容量

给定流 \(f\)，边 \((u,v)\) 的残余容量：

\[c_f(u,v) = c(u,v) - f(u,v)\]

若 \((u,v) \notin E\)，则 \(c_f(u,v) = 0\)（除非 \((v,u) \in E\)，此时 \(c_f(u,v) = f(v,u)\)）

更精确地（CLRS 定义）：

\[c_f(u,v) = \begin{cases} c(u,v) - f(u,v) & (u,v) \in E \\ f(v,u) & (v,u) \in E \\ 0 & \text{否则} \end{cases}\]

残余网络

\(G_f = (V, E_f)\)，\(E_f = \{(u,v) \in V \times V : c_f(u,v) > 0\}\)

\(|E_f| \leq 2|E|\)（原图每条边最多产生正向和反向两条残余边）

增广路径

增广路径：\(G_f\) 中从 \(s\) 到 \(t\) 的简单路径 \(p\)

残余容量（瓶颈容量）：\(c_f(p) = \min_{(u,v) \in p} c_f(u,v)\)

引理 (CLRS Lemma 26.2)

设 \(f\) 是 \(G\) 中的流，\(f'\) 是 \(G_f\) 中的流，则 \(f \uparrow f'\)（\(f\) 被 \(f'\) 增广后）定义为：

\[(f \uparrow f')(u,v) = \begin{cases} f(u,v) + f'(u,v) - f'(v,u) & (u,v) \in E \\ 0 & \text{否则} \end{cases}\]

则 \(f \uparrow f'\) 是 \(G\) 中的流，\(|f \uparrow f'| = |f| + |f'|\)

点击查看证明

容量约束：\((f \uparrow f')(u,v) = f(u,v) + f'(u,v) - f'(v,u)\)

\(f'(u,v) \leq c_f(u,v) = c(u,v) - f(u,v)\)

所以 \((f \uparrow f')(u,v) \leq f(u,v) + c(u,v) - f(u,v) = c(u,v)\)

\(f'(v,u) \leq c_f(v,u) = f(u,v)\)（\(f'(v,u)\) 是反向残余边上的流）

所以 \((f \uparrow f')(u,v) = f(u,v) + f'(u,v) - f'(v,u) \geq f(u,v) - f(u,v) + 0 = 0\)

流量守恒：对 \(u \neq s, t\)，\(f\) 和 \(f'\) 各自满足流量守恒，叠加后仍满足

流值：\(|f \uparrow f'| = |f| + |f'|\)（利用流值的线性性）

---

割 (CLRS 26.2)

定义

割 (Cut)：将 \(V\) 分为 \(S\) 和 \(T = V \setminus S\)，使得 \(s \in S\)，\(t \in T\)

割的净流量：\(f(S, T) = \sum_{u \in S, v \in T} f(u,v) - \sum_{u \in T, v \in S} f(u,v)\)

割的容量：\(c(S, T) = \sum_{u \in S, v \in T} c(u,v)\)

注意容量只计 \(S\) 到 \(T\) 的正向边，不计反向

最小割：容量最小的割

流值等于净流量 (CLRS Lemma 26.5)

引理：对任意流 \(f\) 和任意割 \((S, T)\)：\(|f| = f(S, T)\)

点击查看证明

\[|f| = f(s, V)\]

由流量守恒，\(f(u, V) = 0\) 对所有 \(u \in S \setminus \{s\}\)

\[f(S, V) = f(s, V) + f(S \setminus \{s\}, V) = |f| + 0 = |f|\]

\[f(S, V) = f(S, S) + f(S, T) = 0 + f(S, T) = f(S, T)\]

（\(f(S, S) = 0\) 因为 \(\sum_{u \in S, v \in S} f(u,v) = \sum_{u \in S, v \in S} f(u,v)\)，正好抵消）

因此 \(|f| = f(S, T)\)

上界 (CLRS Corollary 26.5)

推论：对任意流 \(f\) 和任意割 \((S, T)\)：\(|f| \leq c(S, T)\)

点击查看证明

\[|f| = f(S, T) = \sum_{u \in S, v \in T} f(u,v) - \sum_{u \in T, v \in S} f(u,v)\]

\[\leq \sum_{u \in S, v \in T} f(u,v) \leq \sum_{u \in S, v \in T} c(u,v) = c(S, T)\]

---

最大流最小割定理 (CLRS Theorem 26.6)

定理 (Ford & Fulkerson, 1956)：以下三者等价：

1. \(f\) 是 \(G\) 的最大流
2. 残余网络 \(G_f\) 中不存在增广路径
3. 存在割 \((S, T)\) 使得 \(|f| = c(S, T)\)

点击查看证明

\((1) \Rightarrow (2)\)：

反证：若 \(G_f\) 有增广路径 \(p\)，\(c_f(p) > 0\)

沿 \(p\) 增广得到流 \(f'\)，\(|f'| = |f| + c_f(p) > |f|\)

矛盾于 \(f\) 是最大流

\((2) \Rightarrow (3)\)：

\(G_f\) 中无增广路径。定义

\[S = \{v \in V : G_f \text{ 中存在 } s \leadsto v \text{ 的路径}\}\]

\[T = V \setminus S\]

\(s \in S\)（\(s\) 到自身有空路径），\(t \notin S\)（否则有增广路径，矛盾）

\((S, T)\) 是一个合法割

对任意 \(u \in S, v \in T\)：\(c_f(u,v) = 0\)

（否则 \((u,v) \in E_f\)，从 \(s\) 可达 \(u\)，再走到 \(v\)，则 \(v\) 可达，应在 \(S\) 中，矛盾）

若 \((u,v) \in E\)：\(c_f(u,v) = c(u,v) - f(u,v) = 0\)，所以 \(f(u,v) = c(u,v)\)

若 \((v,u) \in E\)：\(c_f(u,v) = f(v,u) = 0\)

\[|f| = f(S, T) = \sum_{u \in S, v \in T} f(u,v) - \sum_{v \in T, u \in S} f(v,u) = \sum_{u \in S, v \in T} c(u,v) - 0 = c(S, T)\]

\((3) \Rightarrow (1)\)：

由推论 26.5，\(|f| \leq c(S', T')\) 对任意割 \((S', T')\) 成立

\(|f| = c(S, T)\) 意味着 \(f\) 已达到上界

整数流定理

定理 (CLRS Corollary 26.11)：若所有容量为整数，则 Ford-Fulkerson 终止时产生的最大流是整数流（每条边上的流量为整数）

证明：每次增广的残余容量 \(c_f(p)\) 是整数（容量整数 → 流整数 → 残余容量整数）。从全零流开始，每步保持整数性

---

Ford-Fulkerson 方法 (CLRS 26.2)

FORD-FULKERSON(G, s, t):
    for each (u,v) ∈ E:
        f(u,v) ← 0
    while 存在增广路径 p in G_f:
        c_f(p) ← min{c_f(u,v) : (u,v) ∈ p}
        for each (u,v) ∈ p:
            if (u,v) ∈ E:
                f(u,v) ← f(u,v) + c_f(p)
            else:
                f(v,u) ← f(v,u) - c_f(p)
    return f

Ford-Fulkerson 没有指定如何选择增广路径——它是一个方法 (method)而非算法

分析

• 每次增广：\(O(E)\)（BFS 或 DFS 找路径 + 更新流）
• 整数容量时：每次增广至少增加 1，总增广次数 \(\leq |f^*|\)
• 总时间 \(O(E \cdot |f^*|)\)

效率问题

\(O(E \cdot |f^*|)\) 不是输入规模的多项式——\(|f^*|\) 可以指数大

经典反例：

s → u → t    容量 C
s → v → t    容量 C
u → v        容量 1

DFS 可能交替选择经过 \((u,v)\) 和 \((v,u)\) 的路径，每次只增加 1

需要 \(2C\) 次增广（\(C\) 可以是 \(10^9\)），而 BFS 只需 2 次

非整数容量的问题

若容量为无理数，Ford-Fulkerson 可能不终止，且收敛到非最大流值

Ford & Fulkerson (1962) 和 Zwick (1995) 构造了这样的例子

---

Edmonds-Karp 算法 (CLRS 26.2)

BFS 最短增广路径

每次用 BFS 找最短（边数最少）增广路径

定理 (CLRS Theorem 26.8)：增广次数 \(\leq O(VE)\)，总时间 \(O(VE^2)\)

单调性引理 (CLRS Lemma 26.7)

设 \(\delta_f(s, v)\) 为 \(G_f\) 中 \(s\) 到 \(v\) 的 BFS 距离（边数）

引理：在 Edmonds-Karp 算法执行过程中，对所有 \(v \in V \setminus \{s, t\}\)，\(\delta_f(s, v)\) 单调不减

点击查看证明

反证：设增广流 \(f\) 得到 \(f'\)，存在 \(v\) 使 \(\delta_{f'}(s, v) < \delta_f(s, v)\)

在所有这样的 \(v\) 中，取 \(\delta_{f'}(s, v)\) 最小的

设 \(G_{f'}\) 中 \(s\) 到 \(v\) 的最短路径为 \(s \leadsto u \to v\)，\(\delta_{f'}(s, v) = \delta_{f'}(s, u) + 1\)

断言：\(\delta_{f'}(s, u) \geq \delta_f(s, u)\)

因为 \(u\) 不满足反证假设（\(\delta_{f'}(s, u) < \delta_{f'}(s, v)\)，而 \(v\) 是最小的反例）

情况 1：\((u,v) \in E_f\)（即增广前 \((u,v)\) 就在残余网络中）

\[\delta_f(s, v) \leq \delta_f(s, u) + 1 \leq \delta_{f'}(s, u) + 1 = \delta_{f'}(s, v)\]

矛盾于 \(\delta_{f'}(s, v) < \delta_f(s, v)\)

情况 2：\((u,v) \notin E_f\)（增广前 \((u,v)\) 不在残余网络中）

\((u,v)\) 在增广后出现在 \(E_{f'}\) 中，说明增广路径经过了 \((v,u)\)

Edmonds-Karp 使用 BFS 最短路径，所以增广路径上 \(\delta_f(s, v) + 1 = \delta_f(s, u)\)

\[\delta_{f'}(s, v) < \delta_f(s, v) = \delta_f(s, u) - 1 \leq \delta_{f'}(s, u) - 1\]

\[\delta_{f'}(s, v) < \delta_{f'}(s, u) - 1\]

\[\delta_{f'}(s, v) + 1 < \delta_{f'}(s, u)\]

但有 \(\delta_{f'}(s, v) = \delta_{f'}(s, u) + 1\)，矛盾

增广次数分析 (CLRS Theorem 26.8)

点击查看分析

定义：增广路径 \(p\) 中，若边 \((u,v)\) 的残余容量等于 \(c_f(p)\)（瓶颈），称 \((u,v)\) 为关键边 (critical edge)

增广后关键边从 \(E_f\) 中消失（被饱和）

边 \((u,v)\) 成为关键边的次数：

当 \((u,v)\) 第一次成为关键时，它在 BFS 最短路径上：

\[\delta_f(s, v) = \delta_f(s, u) + 1\]

\((u,v)\) 被饱和后消失。要重新出现在残余网络中，需要后续增广路径经过 \((v,u)\)

设此时的流为 \(f'\)：

\[\delta_{f'}(s, u) = \delta_{f'}(s, v) + 1\]

由单调性引理：

\[\delta_{f'}(s, u) = \delta_{f'}(s, v) + 1 \geq \delta_f(s, v) + 1 = \delta_f(s, u) + 2\]

因此 \((u,v)\) 每两次成为关键边之间，\(\delta_f(s, u)\) 至少增加 2

\(\delta_f(s, u)\) 从 \(\geq 0\) 到 \(\leq |V| - 2\)，所以 \((u,v)\) 成为关键边最多 \(|V|/2\) 次

残余网络中最多 \(2|E|\) 条边，关键边总出现次数 \(\leq 2|E| \cdot |V|/2 = |V| \cdot |E|\)

每次增广至少产生一条关键边

因此增广次数 \(\leq |V| \cdot |E| = O(VE)\)

每次增广 \(O(E)\)（BFS + 更新），总时间 \(O(VE^2)\)

最大瓶颈路径版本

每次选残余容量最大的增广路径（用修改的 Dijkstra 算法）

引理：最大流为 \(F\) 的图中，存在残余容量 \(\geq F/|E|\) 的 \(s\)-\(t\) 路径

点击查看证明

将流分解为最多 \(|E|\) 条路径流（流分解定理）

至少一条路径的流量 \(\geq F / |E|\)

该路径上所有边残余容量 \(\geq\) 这条路径的流量 \(\geq F/|E|\)

每次增广后剩余流值至少减少 \(1/|E|\) 的比例

最多 \(O(|E| \log F)\) 次增广

总时间 \(O(|E|^2 \log |V| \log F)\)

---

层次图与 Dinic 算法

层次图

定义：\(G_f\) 的层次图 \(L_G\) 由 BFS 构造

顶点按 BFS 距离分层：\(V_0 = \{s\}, V_1, V_2, \ldots\)

\(L_G\) 中只保留从 \(V_i\) 到 \(V_{i+1}\) 的边（即 BFS 树边和同层前进边）

构造时间 \(O(V + E)\)

阻塞流

阻塞流 (Blocking Flow)：\(L_G\) 中的流 \(f\)，使得 \(L_G\) 中每条 \(s\)-\(t\) 路径上至少有一条边被饱和

最大流一定是阻塞流，但阻塞流不一定是最大流（阻塞流只在层次图中阻塞，残余网络中可能还有更长的增广路径）

Dinic 算法

每个阶段 (phase)： 1. BFS 构造层次图 \(L_G\)（\(O(E)\)） 2. 在 \(L_G\) 中找阻塞流 3. 增广原流，更新残余网络

重复直到 \(t\) 在残余网络中不可达

找阻塞流：DFS + 前进/后退/增广

DINIC-BLOCKING-FLOW(L_G):
    f ← 0, u ← s, path ← [s]

    Advance:
        if u 无出边: goto Retreat
        选出边 (u,v)
        path ← path ∥ [v], u ← v
        if v ≠ t: goto Advance
        if v = t: goto Augment

    Retreat:
        if u = s: return f（阻塞流完成）
        从 L_G 删除 u 及其邻边
        path 去掉末尾, u ← path 的最后顶点
        goto Advance

    Augment:
        δ ← path 上的瓶颈容量
        沿 path 增广 δ
        删除饱和边
        u ← path 中从 s 沿未饱和边可达的最后顶点
        path ← path 截断到 u
        goto Advance

单个阶段的复杂度

• Advance：每次增广或撤退前最多 \(n\) 次前进（层次图最多 \(n\) 层），总 Advance 步数 \(O(mn)\)
• Retreat：最多 \(m + n\) 次（每次删一个顶点或边，总共只有 \(m + n\) 可删）
• Augment：最多 \(m\) 次（每次饱和至少一条边）

单阶段：\(O(mn)\)

阶段数分析

引理：每个阶段后，\(\delta_{f'}(s, t)\)（残余网络中 \(s\) 到 \(t\) 的 BFS 距离）严格增加

点击查看证明

设当前阶段层次图的深度为 \(d = \delta_f(s, t)\)

阻塞流饱和了层次图中每条 \(s\)-\(t\) 路径上至少一条边

在更新后的残余网络 \(G_{f'}\) 中：

1. 原层次图中的长度 \(d\) 路径不再完全可用（至少一条边被饱和）
2. 新增的残余边都是反向边 \((v, u)\)，其中 \(u\) 在比 \(v\) 更低的层。使用反向边意味着”后退”一层，要到达 \(t\) 需要多走至少 2 步来弥补

因此 \(G_{f'}\) 中 \(s\) 到 \(t\) 的最短路径长度 \(\geq d + 1\)

\(\delta_f(s, t) \leq |V| - 1\)，每阶段至少增加 1

因此最多 \(|V| - 1\) 个阶段

总时间

\[O(V \cdot mn) = O(mn^2) = O(V^2 E)\]

更优实现（Sleator-Tarjan 使用 Link-Cut 树找阻塞流）：\(O(mn \log n)\)

详细示例

阶段 1: BFS 层次图 V₀={s}, V₁={1,2}, V₂={3,4}, V₃={t}
        距离 d = 3
阻塞流:
  s→1→3→t: 4 单位
  s→1→4→t: 6 单位
  s→2→4→t: 4 单位
总流量: 14

阶段 2: 新 BFS，距离增加到 d = 4
  s→2→4→3→t: 5 单位
总流量: 14 + 5 = 19

阶段 3: t 在残余网络中不可达，算法终止
最大流 = 19

---

单位容量图

定义：所有边容量 \(c_e = 1\)

引理 1：Dinic 算法在单位容量图上最多 \(O(\min(m^{1/2}, n^{2/3}))\) 个阶段

点击查看 $O(m^{1/2})$ 的证明

设最大流值为 \(F\)。在 \(\sqrt{m}\) 个阶段后，设当前流值为 \(f\)

残余网络中 \(s\) 到 \(t\) 的距离 \(> \sqrt{m}\)

残余网络中的边数 \(\leq 2m\)

最大流值 \(F = f + f_{\text{remaining}}\)，其中 \(f_{\text{remaining}}\) 是残余网络的最大流

残余网络中将流分解为增广路径，每条长度 \(> \sqrt{m}\)

每条路径至少使用 \(\sqrt{m}\) 条边，\(2m\) 条边最多分解 \(2m / \sqrt{m} = 2\sqrt{m}\) 条路径

\(f_{\text{remaining}} \leq 2\sqrt{m}\)

剩余 \(2\sqrt{m}\) 单位流量，每阶段至少增加 1，最多再需 \(2\sqrt{m}\) 个阶段

总阶段数 \(\leq \sqrt{m} + 2\sqrt{m} = O(\sqrt{m})\)

引理 2：单位容量图中，阻塞流可在 \(O(m)\) 时间内找到

因为每条增广路径的瓶颈是 1，增广后路径上所有边饱和，DFS 找到一条路径就增广

每条边最多在一条路径中，总增广 \(O(m)\)

定理：单位容量图的最大流可在 \(O(m \cdot \min(m^{1/2}, n^{2/3}))\) 时间内求解

---

应用

边不相交路径与 Menger 定理

问题：给定有向图 \(G = (V, E)\) 和两个节点 \(s, t\)，找最大数量的边不相交 \(s\)-\(t\) 路径

建模：每条边容量 1，求最大流

Menger 定理 (1927)：

\[\text{最大边不相交 } s\text{-}t \text{ 路径数} = \text{最小 } s\text{-}t \text{ 割的边数}\]

这是最大流最小割定理的直接推论

点击查看证明

流 → 路径：整数最大流值为 \(k\)，整数性定理给出 0-1 流

从 \(s\) 出发，沿 \(f(s, u) = 1\) 的边前进

由流量守恒，每到一个非 \(t\) 节点必有出边 \(f = 1\)

继续直到到达 \(t\)，得到一条路径

每次选未用过的边，重复 \(k\) 次得到 \(k\) 条边不相交路径

路径 → 流：\(k\) 条边不相交路径对应值为 \(k\) 的可行流（每条路径边流量 1，不相交保证容量约束）

最大流 = 最小割 给出 Menger 定理

节点不相交路径：对节点容量限制，将 \(v\) 拆为 \(v_{in}\) 和 \(v_{out}\)，中间边容量 1

二部图最大匹配 (CLRS 26.3)

输入：无向二部图 \(G = (L \cup R, E)\)

匹配：边集 \(M \subseteq E\)，每个节点至多出现在一条边中

最大匹配：基数最大的匹配

建模：

1. 添加源 \(s\)，\(s \to l\) 容量 1（\(\forall l \in L\)）
2. 添加汇 \(t\)，\(r \to t\) 容量 1（\(\forall r \in R\)）
3. \(L\) 到 \(R\) 的边容量 1（有向化）
4. 求最大流

定理 (CLRS Theorem 26.10)：\(G\) 的最大匹配基数等于 \(G'\) 的最大流值

点击查看证明

匹配 → 流：匹配 \(M\)，\(|M| = k\)。对每条匹配边 \((l, r) \in M\)：\(f(s, l) = 1\), \(f(l, r) = 1\), \(f(r, t) = 1\)。流值 \(= k\)

流 → 匹配：整数最大流 \(f\)，值为 \(k\)。取 \(M = \{(l, r) : f(l, r) = 1\}\)

\(L\) 中每个 \(l\)：\(s\) 到 \(l\) 容量 1，最多 1 单位流入 \(l\)，\(l\) 最多在 \(M\) 中出现一次

\(R\) 中每个 \(r\) 同理。\(M\) 是匹配且 \(|M| = k\)

时间复杂度：

算法	时间
Ford-Fulkerson	\(O(VE)\)
Dinic（单位容量）	\(O(E \sqrt{V})\)
Hopcroft-Karp (1973)	\(O(E \sqrt{V})\)

Hopcroft-Karp 本质上就是 Dinic 在二部图上的特化

项目选择 (Project Selection)

有 \(n\) 个项目，项目 \(i\) 收益 \(p_i\)（可能为负，表示成本）

项目间有先决关系：完成 \(j\) 必须先完成 \(i\)

目标：选择利润最大的项目子集，满足先决关系

建模：

• \(s \to i\) 容量 \(p_i\)（\(p_i > 0\) 的项目）
• \(i \to t\) 容量 \(-p_i\)（\(p_i < 0\) 的项目）
• \(i \to j\) 容量 \(\infty\)（先决关系）

最小割将项目分为选中（\(s\) 侧）和未选（\(t\) 侧），\(\infty\) 边保证先决关系

最大利润 \(= \sum_{p_i > 0} p_i - \text{最小割}\)

棒球淘汰问题

棒球淘汰为网络流的应用

棒球赛季进行中，\(n\) 支球队。球队 \(i\) 已赢 \(w_i\) 场，剩余 \(r_i\) 场，球队 \(i\) 和 \(j\) 之间还有 \(g_{ij}\) 场未打

问题：球队 \(x\) 是否已被数学淘汰？即无论剩余比赛结果如何，\(x\) 都不可能赢得最多

简单淘汰

若 \(w_x + r_x < w_i\)（某队已赢场数超过 \(x\) 能达到的最大），\(x\) 已淘汰

非平凡淘汰保证：可能没有单支球队领先到淘汰 \(x\)，但一组球队内部比赛保证了集体领先

设 \(W = w_x + r_x\)（\(x\) 能达到的最大胜场）

构造网络：

• 源 \(s\)
• 对每对 \(i, j\)（\(i, j \neq x\)）有比赛节点 \(g_{ij}\)：\(s \to g_{ij}\) 容量 \(g_{ij}\)
• 对每支球队 \(i \neq x\) 有球队节点：\(g_{ij} \to i\) 和 \(g_{ij} \to j\)，容量 \(\infty\)
• \(i \to t\) 容量 \(W - w_i\)（\(i\) 最多还能赢这么多场而不超过 \(x\)）

定理：\(x\) 被淘汰 \(\Leftrightarrow\) 最大流 \(< \sum_{i < j, i,j \neq x} g_{ij}\)

点击查看证明

若最大流饱和所有源边（\(= \sum g_{ij}\)）：存在一种分配使每支球队赢场 \(\leq W\)，\(x\) 未淘汰

若最大流 \(< \sum g_{ij}\)：最小割 \((S, T)\)。设 \(\bar{T}\) 为 \(T\) 中的球队

\(\bar{T}\) 中球队之间的比赛无法全部分配（割容量不足）

\(\bar{T}\) 的总赢场 \(> |\bar{T}| \cdot W\)，即平均赢场 \(> W\)

无论怎么分配，\(\bar{T}\) 中至少一支球队赢场 \(> W = w_x + r_x\)

---

容量缩放算法

弥合了 Ford-Fulkerson（伪多项式）和 Edmonds-Karp（强多项式）之间的差距

动机

Ford-Fulkerson 的问题：每次增广可能只增加 1 单位流量

想法：限制增广路径的残余容量下界

算法

CAPACITY-SCALING(G, s, t):
    Δ ← 2^⌊log₂ C⌋        // C = max capacity
    f ← 0
    while Δ ≥ 1:
        G_f(Δ) ← Δ-残余网络（只保留 c_f(u,v) ≥ Δ 的边）
        while G_f(Δ) 中存在 s-t 增广路径 p:
            沿 p 增广（瓶颈 ≥ Δ）
            更新 G_f(Δ)
        Δ ← Δ / 2
    return f

分析

引理：每个缩放阶段最多 \(O(E)\) 次增广

点击查看证明

设进入 \(\Delta\) 阶段时最大流值为 \(f^*\)，当前流值为 \(|f|\)

\(f^* - |f|\) 等于 \(G_f\) 中的最大流（残余网络的最大流 = 总最大流 - 当前流）

在 \(2\Delta\) 阶段结束时，\(G_f\) 中所有 \(\geq 2\Delta\) 的边都已被充分利用

\(G_f\) 的最大流 \(\leq\) 最小割容量。在 \(\Delta\)-残余网络中，每条跨割边容量 \(< 2\Delta\)（上一阶段遗留），割中最多 \(E\) 条边

所以 \(f^* - |f| \leq E \cdot 2\Delta\)

每次增广至少增加 \(\Delta\)，本阶段最多 \(\frac{2E\Delta}{\Delta} = 2E\) 次增广

总增广次数：\(O(\log C)\) 个阶段 \(\times\) \(O(E)\) 次/阶段 \(= O(E \log C)\)

每次增广 \(O(E)\)（BFS），总时间 \(O(E^2 \log C)\)

这是弱多项式的（依赖 \(\log C\) 而非 \(C\)），比 Ford-Fulkerson 的 \(O(E \cdot C)\) 好很多

---

流分解定理

定理

流分解定理：任何可行流 \(f\)（值为 \(|f|\)）可以分解为：

• 最多 \(E\) 条 \(s\)-\(t\) 路径流，每条有正流量 \(f_i\)
• 最多 \(E\) 条环流，每条有正流量

路径流量之和 \(= |f|\)，环流不贡献流值

点击查看构造性证明

算法：

1. 若 \(|f| > 0\)：从 \(s\) 出发，沿正流边走。由流量守恒，每个非 \(s\)、非 \(t\) 节点有正流出边。两种情况：
   • 到达 \(t\)：找到一条 \(s\)-\(t\) 路径 \(p\)，路径流量 \(= \min_{e \in p} f(e)\)，减去该流
   • 回到已访问节点：找到一个环 \(C\)，环流量 \(= \min_{e \in C} f(e)\)，减去该流
2. 若 \(|f| = 0\) 但仍有正流边：必有环流，同上处理

每次至少消除一条边的流量（瓶颈边变为 0），最多 \(|E|\) 次

应用

• 证明整数流定理：整数容量 → 存在整数最大流
• Menger 定理：整数流分解为路径
• 分析增广路径算法的复杂度

---

附录

算法复杂度总结

算法	时间复杂度	特点
Ford-Fulkerson	\(O(E \cdot |f^*|)\)	不指定路径选择
Edmonds-Karp (BFS)	\(O(VE^2)\)	最短增广路径
Edmonds-Karp (最大瓶颈)	\(O(E^2 \log V \log F)\)	最大瓶颈路径
Dinic	\(O(V^2 E)\)	阻塞流
Dinic (单位容量)	\(O(E \sqrt{V})\)	单位容量特化
Push-Relabel (FIFO)	\(O(V^3)\)	预流推进
King-Rao-Tarjan	\(O(VE \log_{V^2/E} V)\)	理论最优之一
Chen et al. (2022)	\(\tilde{O}(m^{1+o(1)})\)	几乎线性

网络流的历史

年份	算法/定理	复杂度
1927	Menger 定理	—
1931	König 定理	—
1935	Hall 定理	—
1956	Ford-Fulkerson	\(O(mF)\)
1969	Edmonds-Karp	\(O(VE^2)\)
1970	Dinic	\(O(V^2E)\)
1973	Hopcroft-Karp	\(O(E\sqrt{V})\)
1974	Karzanov	\(O(V^3)\)
1986	Goldberg-Tarjan (Push-Relabel)	\(O(VE \log(V^2/E))\)
1997	Goldberg-Rao	\(O(\min(V^{2/3}, E^{1/2}) \cdot E \log(V^2/E) \log U)\)
2022	Chen, Kyng, Liu, Peng et al.	\(\tilde{O}(m^{1+o(1)})\)

2022 年 Chen 等人的突破性成果证明了最大流可以在几乎线性时间内求解