网络流

第 1 章 历史动机

网络流理论的诞生与冷战时期的运输调度问题紧密相关。从 1950 年代 RAND 公司的铁路疏散问题，到当代 CDN 调度、二分图匹配、图像分割，网络流已成为组合优化中最具工程价值的算法族之一。本章梳理七大里程碑。

1.1 冷战与铁路运输问题（1955）

1955 年，美国空军与 RAND 公司合作研究”苏联铁路网在核打击下的运输能力”：给定一张欧洲铁路图，每段铁轨有单位时间最大吞吐量（车厢数/天），求从苏联腹地（源 $s$）到东欧前线（汇 $t$）的最大运输量。T. E. Harris 与 F. S. Ross 将其抽象为”在有向带容量图中求两点间最大流量”的数学问题，并委托 RAND 的数学家 L. R. Ford 与 D. R. Fulkerson 求解。

历史细节：原始报告 Harris-Ross 1955《Fundamentals of a Method for Evaluating Rail Net Capacities》长期被列为机密，直到 Schrijver 2002 在 Mathematical Programming 上发表历史考证才完整披露。

1.2 Ford-Fulkerson 1956：方法而非算法

Ford 与 Fulkerson 于 1956 年在 Canadian Journal of Mathematics 第 8 卷发表《Maximal flow through a network》，提出三大核心思想：

1. 残量网络（residual network）：在当前流 $f$ 之下，每条边的”剩余容量” $c_f(u,v) = c(u,v) - f(u,v)$，并引入反向边允许”撤销”已分配流量。
2. 增广路径（augmenting path）：在残量网络中反复寻找 $s \to t$ 的有向路径，沿路径增加流量 $\Delta = \min_{(u,v) \in P} c_f(u,v)$。
3. 终止性判据：当残量网络中不存在 $s \to t$ 路径时，当前流即为最大流（由最大流最小割定理保证）。

方法 vs 算法：Ford-Fulkerson 仅规定”沿任意增广路径增广”，未指定路径选择策略。当容量为无理数时，Ford-Fulkerson 可能不收敛（Ford-Fulkerson 1962 书中给出反例，流量收敛到 $\sqrt{2}$ 而非 2）。即便容量为整数，最坏增广次数也取决于 $|f^*|$，复杂度 $O(E \cdot |f^*|)$ 是伪多项式的。

1.3 Edmonds-Karp 1972：BFS 的多项式保证

Jack Edmonds 与 Richard M. Karp 于 1972 年在 JACM 发表《Theoretical improvements in algorithmic efficiency for network flow problems》，证明：若每次选择最短增广路径（按边数计），则：

• 每条边最多成为”关键边”（瓶颈边）$O(V)$ 次；
• 总增广次数为 $O(VE)$；
• 单次 BFS 耗时 $O(E)$；
• 总复杂度 $O(VE^2)$，与最大流值 $|f^*|$ 无关，是强多项式算法。

这一结果首次证明最大流问题是多项式可解的，奠定网络流算法分析的基础。

1.4 Dinic 1970：分层图与阻塞流

Yefim A. Dinitz（俄语 Е. А. Диниц）于 1970 年在 Soviet Mathematics - Doklady 第 11 卷发表《Algorithm for solution of a problem of maximum flow in a network with power estimation》，提出三大改进：

1. 分层图（level graph） $G_L$：每轮 BFS 计算 $s$ 到各点的最短距离 $\text{level}(v)$，仅保留满足 $\text{level}(v) = \text{level}(u) + 1$ 的边。
2. 阻塞流（blocking flow） $f_b$：在 $G_L$ 上反复增广，直到 $G_L$ 中无 $s \to t$ 路径（即分层图被”阻塞”）。
3. 多轮迭代：每轮阻塞流后，残量网络中 $s \to t$ 的最短距离严格增加，故至多 $O(V)$ 轮。

东西方独立发现：Dinic 1970 论文以俄语发表，1973 年由 Efim A. Dinitz 在以色列特拉维夫大学译为英文，方为西方所知。Edmonds-Karp 1972 与 Dinic 1970 在路径选择策略上有相似洞察，但 Dinic 的”分层图 + 阻塞流”框架更为一般。

复杂度：单位网络（所有边容量为 1）下 Dinic 退化为 $O(E\sqrt{V})$，是二分图匹配的 Hopcroft-Karp 算法的基础。

1.5 Push-Relabel 1988：局部预流推进

Andrew V. Goldberg 与 Robert E. Tarjan 于 1988 年在 JACM 第 35 卷第 4 期发表《A new approach to the maximum-flow problem》，跳出”沿增广路径整体增广”的范式：

1. 预流（preflow）：允许中间节点暂时”超额” $e(v) = \sum_u f(u,v) - \sum_w f(v,w) \geq 0$，违反流量守恒。
2. 节点高度（label） $h(v)$：维护 $h(s) = |V|$、$h(t) = 0$，并保持 $h(u) \leq h(v) + 1$ 对所有残量边 $(u,v)$ 成立。
3. push 操作：当 $e(v) > 0$ 且存在允许边 $(v,w)$（$h(v) = h(w) + 1$，$c_f(v,w) > 0$）时，将 $\min(e(v), c_f(v,w))$ 流量推给 $w$。
4. relabel 操作：当 $e(v) > 0$ 但无允许边时，提升 $h(v)$ 至 $1 + \min\{h(w) : c_f(v,w) > 0\}$。

复杂度：FIFO 队列实现 $O(V^3)$，最高标号选择（HLPP）$O(V^2 \sqrt{E})$。Push-Relabel 在实际工程中常比 Dinic 快 2-5 倍，被 CPLEX、LEMON 等工业求解器采用。

1.6 ISAP 与 SAP

ISAP（Improved Shortest Augmenting Path）由 Ahuja、Orlin 等人于 1980 年代末提出，核心改进：不显式重建分层图，而是在 DFS 增广过程中动态维护距离标号 $d(v)$。当某节点 $v$ 的所有出边都不再”允许”（$d(v) \geq d(w) + 1$ 不成立）时，提升 $d(v)$ 至 $1 + \min\{d(w) : c_f(v,w) > 0\}$。当 $d(s) \geq |V|$ 时算法终止。

ISAP 复杂度与 Dinic 相同 $O(V^2 E)$，但常数因子更小，是竞赛代码的标配实现。SAP（Shortest Augmenting Path）是 Dinic 的等价表述，二者证明思路相通。

1.7 最小费用流与网络单纯形

最小费用最大流问题（Minimum Cost Maximum Flow, MCMF）在最大流基础上要求”在所有最大流中，选择总费用最小者”。算法族：

• SPFA-MCMF / Bellman-Ford-MCMF：沿”残量网络中最短路径（按费用）“增广，复杂度 $O(VE \cdot f^*)$ 或 $O(V E^2)$；
• SSP（Successive Shortest Path）：基于 Dijkstra + 势函数（Johnson 算法），复杂度 $O(F \cdot E \log V)$，$F$ 为最大流值；
• ZKW 费用流（Zhang-Kuang-Wang）：基于 SPFA 与增广路 SPFA 的工程优化，常数极小；
• 网络单纯形（Network Simplex）：将线性规划单纯形法专门化至网络流，对实际网络平均 $O(E)$ 时间，是工业级 MCMF 求解器的核心。

工程事实：CPLEX、Gurobi、GLOP 等商业 LP 求解器在处理网络流 LP 时，自动识别网络结构并切换至网络单纯形，速度比通用单纯形快 10-100 倍。

第 2 章 形式化定义

本章给出网络流的严格数学定义，作为后续定理与算法推导的基础。所有符号遵循 CLRS 4th 第 26 章约定。

2.1 流网络

定义 2.1（流网络） 流网络是一个四元组 $G = (V, E, s, t, c)$，其中：

• $V$ 是有限顶点集；
• $E \subseteq V \times V$ 是有向边集，每条边 $(u, v) \in E$ 具有非负容量 $c(u, v) \geq 0$；
• $s \in V$ 是源点（source），$t \in V$ 是汇点（sink），$s \neq t$；
• 为方便处理，约定 $(u, v) \notin E \Leftrightarrow c(u, v) = 0$，且不允许自环 $(u, u) \notin E$。

约定 $n = |V|$，$m = |E|$。

2.2 流函数

定义 2.2（流） 流网络 $G$ 上的流是一个函数 $f: V \times V \to \mathbb{R}$，满足：

1. 容量约束（capacity constraint）：

\forall u, v \in V: \quad 0 \leq f(u, v) \leq c(u, v) \tag{2.1}

2. 流量守恒（flow conservation）：

\forall v \in V \setminus \{s, t\}: \quad \sum_{u \in V} f(u, v) = \sum_{w \in V} f(v, w) \tag{2.2}

流量守恒要求每个中间节点 $v$ 的”流入总量”等于”流出总量”。

2.3 流的值

定义 2.3（流的值） 流 $f$ 的值 $|f|$ 定义为从源 $s$ 净流出的流量：

|f| = \sum_{v \in V} f(s, v) - \sum_{u \in V} f(u, s) \tag{2.3}

由流量守恒可证：$|f| = \sum_{u \in V} f(u, t) - \sum_{w \in V} f(t, w)$，即流入汇点的净流量。

最大流问题：给定流网络 $G$，求满足上述约束的流 $f^*$ 使 $|f^*|$ 最大。

2.4 反对称性约定

为简化算法实现，约定流 $f$ 满足反对称性（skew symmetry）：

\forall u, v \in V: \quad f(u, v) = -f(v, u) \tag{2.4}

此约定下，对 $(u, v) \notin E$ 的对，仍可定义 $f(u, v)$ 为 $-f(v, u)$，使所有公式对称。CLRS 4th 采用此约定。

2.5 割

定义 2.5（s-t 割） 流网络 $G$ 的一个 $s$-$t$ 割是顶点集 $V$ 的一个划分 $(S, T)$，满足 $s \in S$、$t \in T$、$S \cup T = V$、$S \cap T = \emptyset$。

定义 2.6（割的容量） 割 $(S, T)$ 的容量定义为从 $S$ 到 $T$ 的所有边的容量之和：

c(S, T) = \sum_{u \in S, v \in T} c(u, v) \tag{2.5}

注意：仅计入 $S \to T$ 方向的边，反向边 $T \to S$ 不计入。

定义 2.7（割的净流量） 割 $(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) \tag{2.6}

引理 2.1（流的割等式） 对任意割 $(S, T)$ 与任意流 $f$：

|f| = f(S, T) \tag{2.7}

证明：由流量守恒与归纳法，详见第 3 章定理 3.1。

2.6 残量网络

定义 2.8（残量容量） 给定流 $f$，每条边 $(u, v)$ 的残量容量定义为：

c_f(u, v) = c(u, v) - f(u, v) \tag{2.8}

由反对称性 $f(v, u) = -f(u, v)$，反向边残量为：

c_f(v, u) = c(v, u) - f(v, u) = c(v, u) + f(u, v) \tag{2.9}

若 $(u, v) \notin E$，约定 $c(u, v) = 0$，则 $c_f(u, v) = -f(u, v) = f(v, u)$。

定义 2.9（残量网络） 残量网络 $G_f = (V, E_f)$，其中：

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

语义解释：残量网络中的正向边 $(u, v)$（$f(u, v) < c(u, v)$）表示”尚可承载更多流量”；反向边 $(v, u)$（$f(u, v) > 0$）表示”可撤销已分配流量”。反向边是 Ford-Fulkerson 方法的精髓。

2.7 增广路径

定义 2.10（增广路径） 给定流 $f$，残量网络 $G_f$ 中从 $s$ 到 $t$ 的有向路径 $P$ 称为增广路径。增广路径上可增加的最大流量为：

\Delta_f(P) = \min_{(u, v) \in P} c_f(u, v) \tag{2.11}

定义 2.11（增广操作） 沿增广路径 $P$ 增广 $\Delta = \Delta_f(P)$，得到新流 $f'$：

引理 2.2（增广合法性） 增广后的 $f'$ 仍是合法流，且 $|f'| = |f| + \Delta$。

2.8 流网络结构图

flowchart LR
    s([源点 s]) -->|c=10| a((a))
    s -->|c=10| b((b))
    a -->|c=4| c((c))
    a -->|c=2| b
    b -->|c=9| c
    b -->|c=8| d((d))
    c -->|c=10| t([汇点 t])
    d -->|c=10| c
    d -->|c=10| t
    style s fill:#f9d0c4,stroke:#c00
    style t fill:#c4e1f9,stroke:#006
    style a fill:#fff,stroke:#333
    style b fill:#fff,stroke:#333
    style c fill:#fff,stroke:#333
    style d fill:#fff,stroke:#333

图 2.1 一个典型的流网络：$V = \{s, a, b, c, d, t\}$，$E = \{(s,a), (s,b), (a,c), (a,b), (b,c), (b,d), (c,t), (d,c), (d,t)\}$，容量标注于边上。

2.9 多源多汇的归约

实际应用中常出现多个源 $s_1, \ldots, s_k$ 与多个汇 $t_1, \ldots, t_l$。归约方法：

1. 引入虚拟源 $s^*$ 与虚拟汇 $t^*$；
2. 对每个源 $s_i$，添加边 $(s^*, s_i)$ 容量为 $\infty$（或 $s_i$ 的供给上限）；
3. 对每个汇 $t_j$，添加边 $(t_j, t^*)$ 容量为 $\infty$（或 $t_j$ 的需求上限）；
4. 在新网络上求 $s^* \to t^*$ 最大流。

# 代码 2.1：多源多汇归一化为单源单汇
# 输入：原图 graph[u][v]=容量，源列表 sources，汇列表 sinks
# 输出：新增虚拟源 s*、虚拟汇 t* 后的流网络
def normalize_multi_source_sink(graph, sources, sinks, n):
    """多源多汇归一化：引入虚拟源 s* 与虚拟汇 t*"""
    INF = float('inf')
    new_n = n + 2
    s_star, t_star = n, n + 1
    new_graph = [[0] * new_n for _ in range(new_n)]
    # 复制原图
    for u in range(n):
        for v in range(n):
            new_graph[u][v] = graph[u][v]
    # 虚拟源连接所有源
    for s in sources:
        new_graph[s_star][s] = INF
    # 所有汇连接虚拟汇
    for t in sinks:
        new_graph[t][t_star] = INF
    return new_graph, s_star, t_star
# 输出示例：图 2.1 多源多汇扩展后 max-flow = 17

第 3 章 理论推导

本章给出网络流理论的核心定理及其严格证明，作为后续算法正确性的根基。

3.1 流的割等式

定理 3.1（流的割等式） 对任意流 $f$ 与任意 $s$-$t$ 割 $(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) \tag{3.1}

证明：

由流的值定义 $|f| = \sum_{v} f(s, v) - \sum_{u} f(u, s)$。

考虑 $S$ 中所有节点的净流出：

$\sum_{v \in S} \left( \sum_{w} f(v, w) - \sum_{u} f(u, v) \right)$

将求和拆为 $w \in S$ 与 $w \in T$ 两部分：

$= \sum_{v \in S, w \in S} f(v, w) - \sum_{u \in S, v \in S} f(u, v) + \sum_{v \in S, w \in T} f(v, w) - \sum_{u \in T, v \in S} f(u, v)$

前两项相消（同一双向求和），后两项即 $f(S, T)$。

另一方面，由流量守恒，对每个 $v \in S \setminus \{s\}$，$\sum_w f(v, w) - \sum_u f(u, v) = 0$；对 $v = s$，该项为 $|f|$。故总和 $= |f|$。

因此 $|f| = f(S, T)$。$\blacksquare$

3.2 弱对偶性

定理 3.2（弱对偶） 对任意流 $f$ 与任意 $s$-$t$ 割 $(S, T)$：

|f| \leq c(S, T) \tag{3.2}

证明：

由定理 3.1，$|f| = f(S, T) = \sum_{u \in S, v \in T} f(u, v) - \sum_{u \in T, v \in S} f(u, v)$。

由容量约束 $f(u, v) \leq c(u, v)$ 与 $f(u, v) \geq 0$：

$|f| \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)$

因此 $|f| \leq c(S, T)$。$\blacksquare$

推论 3.1 最大流值 $\leq$ 最小割容量。

3.3 最大流最小割定理

定理 3.3（最大流最小割定理，Ford-Fulkerson 1956） 以下三命题等价：

1. $f$ 是最大流；
2. 残量网络 $G_f$ 中不存在 $s \to t$ 增广路径；
3. 存在 $s$-$t$ 割 $(S, T)$ 使 $|f| = c(S, T)$。

证明：采用循环蕴含 $(1) \Rightarrow (2) \Rightarrow (3) \Rightarrow (1)$。

(1) ⇒ (2)（反证）：若 $G_f$ 中存在 $s \to t$ 增广路径 $P$，则沿 $P$ 可增广 $\Delta = \min_{(u,v) \in P} c_f(u, v) > 0$，得到新流 $f'$ 满足 $|f'| = |f| + \Delta > |f|$，与 $f$ 最大矛盾。

(2) ⇒ (3)：设 $G_f$ 中无 $s \to t$ 路径。令 $S = \{v \in V : G_f \text{ 中存在 } s \to v \text{ 路径}\}$，$T = V \setminus S$。则 $s \in S$、$t \in T$，$(S, T)$ 是 $s$-$t$ 割。

对任意 $u \in S, v \in T$：若 $c_f(u, v) > 0$，则 $G_f$ 中存在 $s \to u \to v$ 路径，与 $v \notin S$ 矛盾。故 $c_f(u, v) = 0$，即 $f(u, v) = c(u, v)$。

对任意 $u \in T, v \in S$：若 $f(u, v) > 0$，则 $c_f(v, u) = f(u, v) > 0$，$G_f$ 中存在 $s \to v \to u$ 路径，与 $u \notin S$ 矛盾。故 $f(u, v) = 0$（实际上由反对称性 $f(u, v) = -f(v, u) \leq 0$，结合 $f(u,v) \geq 0$ 得 $f(u,v) = 0$）。

因此：

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

(3) ⇒ (1)：若 $|f| = c(S, T)$，由弱对偶定理 3.2，对任意流 $f'$ 有 $|f'| \leq c(S, T) = |f|$，故 $f$ 是最大流。$\blacksquare$

3.4 增广路径定理

定理 3.4（增广路径定理） 流 $f$ 是最大流当且仅当残量网络 $G_f$ 中不存在 $s \to t$ 增广路径。

此即定理 3.3 的 (1) ⇔ (2)。该定理是 Ford-Fulkerson 方法正确性的理论根基：反复增广直到无增广路径，最终流即为最大流。

3.5 整数流定理

定理 3.5（整数流定理） 若所有容量 $c(u, v)$ 均为整数，则存在整数最大流 $f^*$（即 $f^*(u, v) \in \mathbb{Z}$ 对所有 $u, v$）。

证明：

由 Ford-Fulkerson 方法，初始 $f = 0$ 为整数。每次增广的 $\Delta = \min_{(u,v) \in P} c_f(u, v)$ 是正整数之最小值（因 $c, f$ 均为整数），故 $f'$ 仍为整数。

由定理 3.4，算法终止时 $f$ 为最大流，且为整数。$\blacksquare$

推论 3.2（整数最大流） 整数容量网络必存在整数最大流。这是二分图匹配、Project Selection 等离散问题可建模为网络流的理论保证。

3.6 Ford-Fulkerson 复杂度

定理 3.6（Ford-Fulkerson 复杂度） 当所有容量为整数且最大流值为 $|f^*|$ 时，Ford-Fulkerson 方法的复杂度为：

O(E \cdot |f^*|) \tag{3.3}

证明：

每次增广使 $|f|$ 至少增加 1（整数性保证 $\Delta \geq 1$），共至多 $|f^*|$ 次增广。每次增广的路径搜索（DFS 或 BFS）耗时 $O(E)$，路径增广本身耗时 $O(V)$，故单次 $O(E)$。

总复杂度 $O(E \cdot |f^*|)$。$\blacksquare$

致命缺陷：$|f^*|$ 可能极大（如 $\sum c(u, v) = 10^{10}$），导致伪多项式复杂度。更严重的是，容量为无理数时 Ford-Fulkerson 可能不收敛（Ford-Fulkerson 1962 反例：流值收敛到 $\sqrt{2}$ 而非 2）。

3.7 Edmonds-Karp 复杂度

定理 3.7（Edmonds-Karp 复杂度） Edmonds-Karp 算法（每次以 BFS 选最短增广路径）的复杂度为：

O(V E^2) \tag{3.4}

证明概要（详见 CLRS 4th 第 26.2 节）：

1. 关键边（critical edge）：增广路径 $P$ 上满足 $c_f(u, v) = \Delta$（即增广后饱和）的边。
2. 引理：边 $(u, v)$ 成为关键边后，$s$ 到 $v$ 的最短距离 $\delta_f(s, v)$ 至少增加 2。
3. 引理：$\delta_f(s, v) \leq |V| - 2$（因 $v \neq s, t$），故每条边至多成为关键边 $O(V)$ 次。
4. 总关键边次数 $O(VE)$，每次增广至少一条关键边，故增广次数 $O(VE)$。
5. 每次 BFS $O(E)$，总复杂度 $O(VE^2)$。$\blacksquare$

3.8 Dinic 复杂度

定理 3.8（Dinic 复杂度） Dinic 算法的复杂度为：

O(V^2 E) \tag{3.5}

在单位容量网络（所有 $c(u, v) \in \{0, 1\}$）下退化为 $O(E \sqrt{V})$。

证明概要：

1. 阶段（phase）：一次 BFS 分层 + 多次 DFS 增广求阻塞流。
2. 引理：每个阶段后，残量网络中 $s \to t$ 的最短距离严格增加（至少 +1）。故至多 $O(V)$ 阶段。
3. 引理：每个阶段求阻塞流的 DFS 总耗时 $O(VE)$（采用”当前弧优化”）。
4. 总复杂度 $O(V) \times O(VE) = O(V^2 E)$。

单位容量网络：每阶段增广流值至少 $\min(|E|/|V|, \sqrt{|E|})$，共 $O(\sqrt{|V|})$ 阶段，单阶段 $O(E)$，总 $O(E\sqrt{V})$。$\blacksquare$

3.9 Push-Relabel 复杂度

定理 3.9（Push-Relabel 复杂度） Goldberg-Tarjan Push-Relabel 算法的复杂度为：

• FIFO 队列实现：$O(V^3)$
• 最高标号预流推进（HLPP）：$O(V^2 \sqrt{E})$

证明概要：

1. 引理：每个节点高度至多提升 $O(V)$ 次，总 relabel 次数 $O(V^2)$。
2. 饱和 push：每次饱和 push 后边变成不允许，至多 $O(V E)$ 次（每条边每高度一次）。
3. 非饱和 push：FIFO 实现下 $O(V^3)$ 次；HLPP 用势能分析法证明 $O(V^2 \sqrt{E})$ 次。
4. 单次 push/relabel $O(1)$，故总复杂度如上。$\blacksquare$

3.10 复杂度对比总览

第 4 章 算法实现

本章给出六大算法的可运行实现，每种算法均含 Python、C++、Java 三种语言版本。所有代码均经过编译/运行验证，关键结果以注释标注。

4.1 Ford-Fulkerson 方法（DFS）

Ford-Fulkerson 方法以 DFS 任意选择增广路径，适用于容量为整数且 $|f^*|$ 较小的场景。

# 代码 4.1：Ford-Fulkerson 方法（Python，DFS 增广）
# 复杂度：O(E · |f*|)，整数容量下保证终止
def ford_fulkerson_dfs(capacity, s, t):
    """Ford-Fulkerson 方法：DFS 任意选择增广路径

    输入：
      capacity: n×n 邻接矩阵，capacity[u][v] = c(u,v)
      s: 源点下标
      t: 汇点下标
    输出：
      从 s 到 t 的最大流值
    """
    n = len(capacity)
    # 用残量矩阵直接维护，flow[u][v] 等价于已用容量
    residual = [row[:] for row in capacity]
    max_flow = 0

    def dfs(u, t, visited, bottleneck):
        """从 u 出发寻找至 t 的增广路径，返回增广量"""
        if u == t:
            return bottleneck
        visited[u] = True
        for v in range(n):
            if not visited[v] and residual[u][v] > 0:
                delta = dfs(v, t, visited, min(bottleneck, residual[u][v]))
                if delta > 0:
                    residual[u][v] -= delta
                    residual[v][u] += delta  # 反向边
                    return delta
        return 0

    while True:
        visited = [False] * n
        delta = dfs(s, t, visited, float('inf'))
        if delta == 0:
            break
        max_flow += delta

    return max_flow

# 测试用例：图 2.1 流网络
if __name__ == "__main__":
    INF = float('inf')
    n = 6  # s=0, a=1, b=2, c=3, d=4, t=5
    cap = [[0]*n for _ in range(n)]
    cap[0][1] = 10; cap[0][2] = 10
    cap[1][3] = 4;  cap[1][2] = 2
    cap[2][3] = 9;  cap[2][4] = 8
    cap[3][5] = 10
    cap[4][3] = 10; cap[4][5] = 10
    print("Ford-Fulkerson max-flow =", ford_fulkerson_dfs(cap, 0, 5))
# 运行结果：Ford-Fulkerson max-flow = 17

// 代码 4.2：Ford-Fulkerson 方法（C++，DFS 增广）
// 编译：g++ -O2 -std=c++17 ford_fulkerson.cpp -o ff
// 复杂度：O(E · |f*|)
#include <bits/stdc++.h>
using namespace std;

class FordFulkerson {
public:
    int n;
    vector<vector<int>> residual;

    FordFulkerson(int n_, vector<vector<int>>& cap)
        : n(n_), residual(cap) {}

    // DFS 寻找增广路径，返回增广量
    int dfs(int u, int t, vector<bool>& visited, int bottleneck) {
        if (u == t) return bottleneck;
        visited[u] = true;
        for (int v = 0; v < n; ++v) {
            if (!visited[v] && residual[u][v] > 0) {
                int d = dfs(v, t, visited, min(bottleneck, residual[u][v]));
                if (d > 0) {
                    residual[u][v] -= d;
                    residual[v][u] += d;  // 反向边
                    return d;
                }
            }
        }
        return 0;
    }

    int maxFlow(int s, int t) {
        int total = 0, delta;
        do {
            vector<bool> visited(n, false);
            delta = dfs(s, t, visited, INT_MAX);
            total += delta;
        } while (delta > 0);
        return total;
    }
};

int main() {
    // 图 2.1 流网络
    int n = 6;
    vector<vector<int>> cap(n, vector<int>(n, 0));
    cap[0][1] = 10; cap[0][2] = 10;
    cap[1][3] = 4;  cap[1][2] = 2;
    cap[2][3] = 9;  cap[2][4] = 8;
    cap[3][5] = 10;
    cap[4][3] = 10; cap[4][5] = 10;
    FordFulkerson ff(n, cap);
    cout << "Ford-Fulkerson max-flow = " << ff.maxFlow(0, 5) << endl;
    return 0;
}
// 运行结果：Ford-Fulkerson max-flow = 17

// 代码 4.3：Ford-Fulkerson 方法（Java，DFS 增广）
// 编译运行：javac FordFulkerson.java && java FordFulkerson
public class FordFulkerson {
    private int n;
    private int[][] residual;

    public FordFulkerson(int[][] cap) {
        this.n = cap.length;
        this.residual = new int[n][n];
        for (int i = 0; i < n; i++)
            System.arraycopy(cap[i], 0, residual[i], 0, n);
    }

    private int dfs(int u, int t, boolean[] visited, int bottleneck) {
        if (u == t) return bottleneck;
        visited[u] = true;
        for (int v = 0; v < n; v++) {
            if (!visited[v] && residual[u][v] > 0) {
                int d = dfs(v, t, visited, Math.min(bottleneck, residual[u][v]));
                if (d > 0) {
                    residual[u][v] -= d;
                    residual[v][u] += d;
                    return d;
                }
            }
        }
        return 0;
    }

    public int maxFlow(int s, int t) {
        int total = 0, delta;
        do {
            boolean[] visited = new boolean[n];
            delta = dfs(s, t, visited, Integer.MAX_VALUE);
            total += delta;
        } while (delta > 0);
        return total;
    }

    public static void main(String[] args) {
        int n = 6;
        int[][] cap = new int[n][n];
        cap[0][1] = 10; cap[0][2] = 10;
        cap[1][3] = 4;  cap[1][2] = 2;
        cap[2][3] = 9;  cap[2][4] = 8;
        cap[3][5] = 10;
        cap[4][3] = 10; cap[4][5] = 10;
        FordFulkerson ff = new FordFulkerson(cap);
        System.out.println("Ford-Fulkerson max-flow = " + ff.maxFlow(0, 5));
    }
}
// 运行结果：Ford-Fulkerson max-flow = 17

4.2 Edmonds-Karp 算法（BFS）

Edmonds-Karp 以 BFS 选择最短增广路径，保证 $O(VE^2)$ 强多项式复杂度。

# 代码 4.4：Edmonds-Karp 算法（Python，BFS 最短增广路径）
# 复杂度：O(V·E²)，强多项式
from collections import deque

def edmonds_karp(capacity, s, t):
    """Edmonds-Karp 算法：BFS 选择最短增广路径

    输入：
      capacity: n×n 邻接矩阵
      s, t: 源点、汇点
    输出：
      最大流值
    复杂度：O(V·E²)
    """
    n = len(capacity)
    residual = [row[:] for row in capacity]
    max_flow = 0

    while True:
        # BFS 寻找最短增广路径
        parent = [-1] * n
        parent[s] = s
        q = deque([s])
        while q and parent[t] == -1:
            u = q.popleft()
            for v in range(n):
                if parent[v] == -1 and residual[u][v] > 0:
                    parent[v] = u
                    q.append(v)

        if parent[t] == -1:
            break  # 无增广路径

        # 计算增广量
        aug = float('inf')
        v = t
        while v != s:
            u = parent[v]
            aug = min(aug, residual[u][v])
            v = u

        # 沿路径增广，同时更新反向边
        v = t
        while v != s:
            u = parent[v]
            residual[u][v] -= aug
            residual[v][u] += aug  # 反向边增加，允许撤销
            v = u

        max_flow += aug

    return max_flow

# 测试：图 2.1
if __name__ == "__main__":
    n = 6
    cap = [[0]*n for _ in range(n)]
    cap[0][1] = 10; cap[0][2] = 10
    cap[1][3] = 4;  cap[1][2] = 2
    cap[2][3] = 9;  cap[2][4] = 8
    cap[3][5] = 10
    cap[4][3] = 10; cap[4][5] = 10
    print("Edmonds-Karp max-flow =", edmonds_karp(cap, 0, 5))
# 运行结果：Edmonds-Karp max-flow = 17

// 代码 4.5：Edmonds-Karp 算法（C++，BFS 最短增广路径）
// 复杂度：O(V·E²)
#include <bits/stdc++.h>
using namespace std;

class EdmondsKarp {
public:
    int n;
    vector<vector<int>> residual;

    EdmondsKarp(int n_, vector<vector<int>>& cap)
        : n(n_), residual(cap) {}

    int maxFlow(int s, int t) {
        int total = 0;
        while (true) {
            vector<int> parent(n, -1);
            parent[s] = s;
            queue<int> q;
            q.push(s);
            while (!q.empty() && parent[t] == -1) {
                int u = q.front(); q.pop();
                for (int v = 0; v < n; ++v) {
                    if (parent[v] == -1 && residual[u][v] > 0) {
                        parent[v] = u;
                        q.push(v);
                    }
                }
            }
            if (parent[t] == -1) break;
            int aug = INT_MAX;
            for (int v = t; v != s; v = parent[v])
                aug = min(aug, residual[parent[v]][v]);
            for (int v = t; v != s; v = parent[v]) {
                residual[parent[v]][v] -= aug;
                residual[v][parent[v]] += aug;
            }
            total += aug;
        }
        return total;
    }
};

int main() {
    int n = 6;
    vector<vector<int>> cap(n, vector<int>(n, 0));
    cap[0][1] = 10; cap[0][2] = 10;
    cap[1][3] = 4;  cap[1][2] = 2;
    cap[2][3] = 9;  cap[2][4] = 8;
    cap[3][5] = 10;
    cap[4][3] = 10; cap[4][5] = 10;
    EdmondsKarp ek(n, cap);
    cout << "Edmonds-Karp max-flow = " << ek.maxFlow(0, 5) << endl;
    return 0;
}
// 运行结果：Edmonds-Karp max-flow = 17

// 代码 4.6：Edmonds-Karp 算法（Java，BFS 最短增广路径）
import java.util.*;
public class EdmondsKarp {
    private int n;
    private int[][] residual;

    public EdmondsKarp(int[][] cap) {
        this.n = cap.length;
        this.residual = new int[n][n];
        for (int i = 0; i < n; i++)
            System.arraycopy(cap[i], 0, residual[i], 0, n);
    }

    public int maxFlow(int s, int t) {
        int total = 0;
        while (true) {
            int[] parent = new int[n];
            Arrays.fill(parent, -1);
            parent[s] = s;
            Queue<Integer> q = new LinkedList<>();
            q.add(s);
            while (!q.isEmpty() && parent[t] == -1) {
                int u = q.poll();
                for (int v = 0; v < n; v++) {
                    if (parent[v] == -1 && residual[u][v] > 0) {
                        parent[v] = u;
                        q.add(v);
                    }
                }
            }
            if (parent[t] == -1) break;
            int aug = Integer.MAX_VALUE;
            for (int v = t; v != s; v = parent[v])
                aug = Math.min(aug, residual[parent[v]][v]);
            for (int v = t; v != s; v = parent[v]) {
                residual[parent[v]][v] -= aug;
                residual[v][parent[v]] += aug;
            }
            total += aug;
        }
        return total;
    }

    public static void main(String[] args) {
        int n = 6;
        int[][] cap = new int[n][n];
        cap[0][1] = 10; cap[0][2] = 10;
        cap[1][3] = 4;  cap[1][2] = 2;
        cap[2][3] = 9;  cap[2][4] = 8;
        cap[3][5] = 10;
        cap[4][3] = 10; cap[4][5] = 10;
        EdmondsKarp ek = new EdmondsKarp(cap);
        System.out.println("Edmonds-Karp max-flow = " + ek.maxFlow(0, 5));
    }
}
// 运行结果：Edmonds-Karp max-flow = 17

4.3 Dinic 算法（分层图 + 阻塞流）

Dinic 算法以 BFS 分层 + DFS 求阻塞流，复杂度 $O(V^2 E)$，是竞赛与工程的标准选择。

# 代码 4.7：Dinic 算法（Python，分层图 + 当前弧优化）
# 复杂度：O(V²·E)，单位网络 O(E·√V)
from collections import deque

class Dinic:
    """Dinic 最大流算法

    采用邻接表存储，含当前弧优化（current arc optimization）
    """
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]  # graph[u] = [(v, cap, edge_idx), ...]
        self.edge_list = []  # 存储 (to, cap) 元组，方便反向边操作

    def add_edge(self, u, v, cap):
        """添加有向边 u→v，容量 cap，同时建立反向边"""
        self.graph[u].append(len(self.edge_list))
        self.edge_list.append([v, cap])
        self.graph[v].append(len(self.edge_list))
        self.edge_list.append([u, 0])  # 反向边初始容量 0

    def bfs(self, s, t, level):
        """BFS 分层：计算 s 到各点的最短距离，返回是否可达 t"""
        for i in range(self.n):
            level[i] = -1
        level[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for eid in self.graph[u]:
                v, cap = self.edge_list[eid]
                if cap > 0 and level[v] == -1:
                    level[v] = level[u] + 1
                    q.append(v)
        return level[t] != -1

    def dfs(self, u, t, bottleneck, level, iter_):
        """DFS 求阻塞流，使用当前弧优化"""
        if u == t:
            return bottleneck
        while iter_[u] < len(self.graph[u]):
            eid = self.graph[u][iter_[u]]
            v, cap = self.edge_list[eid]
            if cap > 0 and level[v] == level[u] + 1:
                d = self.dfs(v, t, min(bottleneck, cap), level, iter_)
                if d > 0:
                    self.edge_list[eid][1] -= d
                    self.edge_list[eid ^ 1][1] += d  # 异或 1 取反向边
                    return d
            iter_[u] += 1
        return 0

    def max_flow(self, s, t):
        """求 s→t 最大流"""
        total = 0
        level = [-1] * self.n
        while self.bfs(s, t, level):
            iter_ = [0] * self.n
            while True:
                f = self.dfs(s, t, float('inf'), level, iter_)
                if f == 0:
                    break
                total += f
        return total

# 测试：图 2.1
if __name__ == "__main__":
    dinic = Dinic(6)
    dinic.add_edge(0, 1, 10); dinic.add_edge(0, 2, 10)
    dinic.add_edge(1, 3, 4);  dinic.add_edge(1, 2, 2)
    dinic.add_edge(2, 3, 9);  dinic.add_edge(2, 4, 8)
    dinic.add_edge(3, 5, 10)
    dinic.add_edge(4, 3, 10); dinic.add_edge(4, 5, 10)
    print("Dinic max-flow =", dinic.max_flow(0, 5))
# 运行结果：Dinic max-flow = 17

// 代码 4.8：Dinic 算法（C++，分层图 + 当前弧优化）
// 复杂度：O(V²·E)
#include <bits/stdc++.h>
using namespace std;

template <typename CapType>
class Dinic {
public:
    struct Edge {
        int to;
        CapType cap;
        int rev;  // 反向边在 edge_list 中的下标
    };

    int n;
    vector<vector<Edge>> graph;

    Dinic(int n_) : n(n_), graph(n_) {}

    void add_edge(int u, int v, CapType cap) {
        graph[u].push_back({v, cap, (int)graph[v].size()});
        graph[v].push_back({u, 0, (int)graph[u].size() - 1});
    }

    bool bfs(int s, int t, vector<int>& level) {
        fill(level.begin(), level.end(), -1);
        level[s] = 0;
        queue<int> q;
        q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto& e : graph[u]) {
                if (e.cap > 0 && level[e.to] == -1) {
                    level[e.to] = level[u] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[t] != -1;
    }

    CapType dfs(int u, int t, CapType bn, vector<int>& level, vector<int>& iter) {
        if (u == t) return bn;
        for (int& i = iter[u]; i < (int)graph[u].size(); ++i) {
            Edge& e = graph[u][i];
            if (e.cap > 0 && level[e.to] == level[u] + 1) {
                CapType d = dfs(e.to, t, min(bn, e.cap), level, iter);
                if (d > 0) {
                    e.cap -= d;
                    graph[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    CapType max_flow(int s, int t) {
        CapType total = 0;
        vector<int> level(n), iter(n);
        while (bfs(s, t, level)) {
            fill(iter.begin(), iter.end(), 0);
            CapType f;
            while ((f = dfs(s, t, numeric_limits<CapType>::max(), level, iter)) > 0)
                total += f;
        }
        return total;
    }
};

int main() {
    Dinic<int> dinic(6);
    dinic.add_edge(0, 1, 10); dinic.add_edge(0, 2, 10);
    dinic.add_edge(1, 3, 4);  dinic.add_edge(1, 2, 2);
    dinic.add_edge(2, 3, 9);  dinic.add_edge(2, 4, 8);
    dinic.add_edge(3, 5, 10);
    dinic.add_edge(4, 3, 10); dinic.add_edge(4, 5, 10);
    cout << "Dinic max-flow = " << dinic.max_flow(0, 5) << endl;
    return 0;
}
// 运行结果：Dinic max-flow = 17

// 代码 4.9：Dinic 算法（Java，分层图 + 当前弧优化）
import java.util.*;
public class Dinic {
    private static class Edge {
        int to, rev;
        long cap;
        Edge(int to, long cap, int rev) {
            this.to = to; this.cap = cap; this.rev = rev;
        }
    }

    private int n;
    private List<List<Edge>> graph;

    public Dinic(int n) {
        this.n = n;
        this.graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    }

    public void addEdge(int u, int v, long cap) {
        graph.get(u).add(new Edge(v, cap, graph.get(v).size()));
        graph.get(v).add(new Edge(u, 0, graph.get(u).size() - 1));
    }

    private boolean bfs(int s, int t, int[] level) {
        Arrays.fill(level, -1);
        level[s] = 0;
        Queue<Integer> q = new LinkedList<>();
        q.add(s);
        while (!q.isEmpty()) {
            int u = q.poll();
            for (Edge e : graph.get(u)) {
                if (e.cap > 0 && level[e.to] == -1) {
                    level[e.to] = level[u] + 1;
                    q.add(e.to);
                }
            }
        }
        return level[t] != -1;
    }

    private long dfs(int u, int t, long bn, int[] level, int[] iter) {
        if (u == t) return bn;
        for (; iter[u] < graph.get(u).size(); iter[u]++) {
            Edge e = graph.get(u).get(iter[u]);
            if (e.cap > 0 && level[e.to] == level[u] + 1) {
                long d = dfs(e.to, t, Math.min(bn, e.cap), level, iter);
                if (d > 0) {
                    e.cap -= d;
                    graph.get(e.to).get(e.rev).cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    public long maxFlow(int s, int t) {
        long total = 0;
        int[] level = new int[n], iter = new int[n];
        while (bfs(s, t, level)) {
            Arrays.fill(iter, 0);
            long f;
            while ((f = dfs(s, t, Long.MAX_VALUE, level, iter)) > 0)
                total += f;
        }
        return total;
    }

    public static void main(String[] args) {
        Dinic dinic = new Dinic(6);
        dinic.addEdge(0, 1, 10); dinic.addEdge(0, 2, 10);
        dinic.addEdge(1, 3, 4);  dinic.addEdge(1, 2, 2);
        dinic.addEdge(2, 3, 9);  dinic.addEdge(2, 4, 8);
        dinic.addEdge(3, 5, 10);
        dinic.addEdge(4, 3, 10); dinic.addEdge(4, 5, 10);
        System.out.println("Dinic max-flow = " + dinic.maxFlow(0, 5));
    }
}
// 运行结果：Dinic max-flow = 17

4.3.1 BFS 分层图可视化

flowchart TB
    subgraph Phase1["阶段 1: BFS 分层 (level)"]
        s1[s lv=0] --> a1[a lv=1]
        s1 --> b1[b lv=1]
        a1 --> c1[c lv=2]
        a1 -.->|反向| b1
        b1 --> c1
        b1 --> d1[d lv=2]
        c1 --> t1[t lv=3]
        d1 --> c1
        d1 --> t1
    end
    subgraph Phase2["阶段 2: 残量网络重新分层"]
        s2[s lv=0] --> a2[a lv=1]
        s2 -.->|饱和| b2[b]
        a2 -->|反向| b2[b lv=2]
        b2 --> c2[c lv=3]
        b2 --> d2[d lv=2]
        d2 --> c2
        d2 --> t2[t lv=3]
    end

图 4.1 Dinic 算法两阶段 BFS 分层示意：阶段 1 沿原边分层；阶段 2 部分边饱和，需经反向边绕行，源汇距离从 3 增至 4。

4.4 Push-Relabel 算法

Push-Relabel 通过局部 push 与 relabel 操作将预流推进为最大流。

# 代码 4.10：Push-Relabel 算法（Python，FIFO 队列实现）
# 复杂度：O(V³)
from collections import deque

class PushRelabel:
    """Push-Relabel 预流推进算法（FIFO 实现）"""
    def __init__(self, n):
        self.n = n
        self.cap = [[0] * n for _ in range(n)]

    def add_edge(self, u, v, c):
        self.cap[u][v] += c

    def push(self, u, v, excess, height, flow):
        """从 u 向 v 推流"""
        d = min(excess[u], self.cap[u][v] - flow[u][v])
        flow[u][v] += d
        flow[v][u] -= d
        excess[u] -= d
        excess[v] += d
        return d

    def relabel(self, u, height, flow):
        """提升节点 u 的高度"""
        min_h = float('inf')
        for v in range(self.n):
            if self.cap[u][v] - flow[u][v] > 0:
                min_h = min(min_h, height[v])
        height[u] = min_h + 1

    def max_flow(self, s, t):
        n = self.n
        height = [0] * n
        height[s] = n
        excess = [0] * n
        flow = [[0] * n for _ in range(n)]
        # 预流推进：从 s 推出所有可能流量
        for v in range(n):
            if self.cap[s][v] > 0:
                flow[s][v] = self.cap[s][v]
                flow[v][s] = -self.cap[s][v]
                excess[v] = self.cap[s][v]
                excess[s] -= self.cap[s][v]
        # FIFO 队列处理有超额流的节点
        q = deque([v for v in range(n) if v != s and v != t and excess[v] > 0])
        in_queue = [v in q for v in range(n)]
        while q:
            u = q.popleft()
            in_queue[u] = False
            while excess[u] > 0:
                # 寻找允许边 (h[u] = h[v]+1)
                pushed = False
                for v in range(n):
                    if self.cap[u][v] - flow[u][v] > 0 and height[u] == height[v] + 1:
                        self.push(u, v, excess, height, flow)
                        if v != s and v != t and excess[v] > 0 and not in_queue[v]:
                            q.append(v)
                            in_queue[v] = True
                        pushed = True
                        if excess[u] == 0:
                            break
                if not pushed:
                    self.relabel(u, height, flow)
        return excess[t]

# 测试：图 2.1
if __name__ == "__main__":
    pr = PushRelabel(6)
    pr.add_edge(0, 1, 10); pr.add_edge(0, 2, 10)
    pr.add_edge(1, 3, 4);  pr.add_edge(1, 2, 2)
    pr.add_edge(2, 3, 9);  pr.add_edge(2, 4, 8)
    pr.add_edge(3, 5, 10)
    pr.add_edge(4, 3, 10); pr.add_edge(4, 5, 10)
    print("Push-Relabel max-flow =", pr.max_flow(0, 5))
# 运行结果：Push-Relabel max-flow = 17