第 26 章 最大流
本章对应原书第 26 章。把有向图看成管道网络：物料从源点流出，经过容量有限的管道，到汇点被消耗。最多能流多少？这个问题叫最大流。它的核心结论——最大流等于最小割——是组合优化里最漂亮的对偶定理之一，也是第 29 章线性规划对偶的一个具体实例。量化交易里，最大流不直接用于选股或回测，但在资金调拨、保证金划转、订单分配、"带依赖关系的选择问题"这类有网络结构的环节，它能给出精确解和瓶颈诊断。本章重点讲透 Ford-Fulkerson 方法和最大流最小割定理，推送-重贴标签方法讲清思路与复杂度，细节留给原书。
学习目标
读完本章，你应当能够：
- 写出流网络、流、流值、割、割容量的定义，用反平行边拆点、超级源汇等技巧把实际问题建成标准流网络。
- 理解残存网络和增广路径，说清反向残存边为什么代表"抵消"已有的流。
- 证明最大流最小割定理的三条等价表述，并能从最大流结果中读出一个最小割（瓶颈）。
- 掌握 Edmonds-Karp 算法（BFS 增广，\(O(VE^2)\)）及其分析思路；知道推送-重贴标签方法的基本思想和 \(O(V^2E)\)、\(O(V^3)\) 的界。
- 把二分图最大匹配、项目选择（带依赖的选择）问题归约为最大流/最小割，并用于资金调拨、策略上线选择等量化场景。
读前导读
这一章在解决什么问题。 一张由管道组成的网络，每根管道有单位时间的最大通过量（容量）。从源头往终点送东西，最多能送多少？这就是最大流。你最容易代入的场景是资金调拨：钱从几家银行出发，经托管行、主经纪商划转到各交易所，每条通道有当日额度；问今天最多能把多少保证金送到位。与最短路径不同，这里不关心"走哪条路最便宜"，而关心"所有路一起用，总量最多是多少"。
本章最重要的结论是最大流 = 最小割。"割"是把网络一刀切成两半（源头一侧、终点一侧），割的容量是所有从源头侧指向终点侧的管道容量之和。显然，无论怎么送，流量都不可能超过任何一刀切口的容量（东西总得过这道坎）；令人意外的是，最大流恰好等于最窄那一刀的容量。这给了你两样东西：一个上限（不用再试，再怎么调度也只能到这个数）和一份瓶颈清单（想提高上限，就必须扩容这一刀上的通道，扩容别处没用）。这和你熟悉的"对偶"是一类思想：CFA 里说任何一个可行的复制组合给出期权价格的一个界，最优时上下界相等；第 29 章的线性规划对偶会把它说成一般定理。
算法上，核心是 Ford-Fulkerson 方法：反复找一条"还能多送一点"的路径（增广路径）并送满它，直到找不到为止。它有一个反直觉但关键的设计：允许把之前送出的流"退回来"（反向残存边），从而纠正早先的糟糕选择。
需要先想起来的数学。
- 求和记号与双重求和。 \(\sum_{v\in V}f(s,v)\) 表示"对所有顶点 \(v\)，把 \(f(s,v)\) 加起来"，即从 \(s\) 流出的总量。\(\sum_{u\in S}\sum_{v\in T}c(u,v)\) 是"\(u\) 取遍 \(S\)、\(v\) 取遍 \(T\) 的所有组合，把 \(c(u,v)\) 全部加起来"，就像把一张损益表里某几行、某几列交叉的格子加总。见 第 00 册第 07 章 概率中的分析工具。
- 函数与集合记号。 \(f:V\times V\to\mathbb R\) 表示 \(f\) 给每个"有序顶点对" \((u,v)\) 配一个实数，即 \(u\) 送往 \(v\) 的流量。\(V-\{s,t\}\) 是"去掉 \(s\) 和 \(t\) 之后的顶点"，\(A\subseteq L\) 读作"\(A\) 是 \(L\) 的子集"。见 第 00 册第 08 章 读懂数学证明与符号。
- "以下几条等价"的证法。 定理 26.6 说三条命题等价，证明用的是"转圈"：证 (1)⇒(2)、(2)⇒(3)、(3)⇒(1)，三步合起来，任意两条都能互推。\(A\Rightarrow B\) 读作"若 \(A\) 成立则 \(B\) 成立"。同见第 08 章。
- 上界与"取等即最优"。 若对每个可行方案都有"方案值 \(\le\) 某个上限"，而某个方案恰好达到这个上限，那它就是最优的，不必再比较其他方案。例：一个组合的预期收益不可能超过成分资产中的最高收益；若某个组合达到了它，它就是收益最高的组合。最大流最小割的 (3)⇒(1) 就是这个论证。见 第 00 册第 01 章 函数极限与连续。
- 渐近记号。 \(O(VE^2)\) 是"不超过顶点数乘边数平方的常数倍"，详见本册第 03 章；BFS（广度优先搜索，按"离起点几步"一层层扫描）见本册第 22 章。
怎么读这一章。 必读：26.1.1（定义）、26.2.2（残存网络与抵消）、26.2.4（割与最大流最小割定理）、26.6.2 和 26.6.3（资金调拨与策略选择）。26.2.5–26.2.6 读懂"为什么要用 BFS 找路径"即可，引理 26.7 和定理 26.8 的证明第一次可以只看结论。26.3 二分图匹配读懂建模方法和整数性定理。26.4 推送-重贴标签是选读，可以只看 26.4.1 的流体类比；26.5 思考题中 26-3 项目选择值得读，其他可跳过。
26.1 流网络
26.1.1 定义
流网络（flow network）\(G=(V,E)\) 是有向图，每条边 \((u,v)\) 有非负容量（capacity）\(c(u,v)\ge0\)。约定：
- 若 \((u,v)\in E\)，则反向边 \((v,u)\notin E\)（不允许反平行边，后面有绕开的办法）；
- \((u,v)\notin E\) 时 \(c(u,v)=0\)；不允许自环；
- 指定源点（source）\(s\) 和汇点（sink）\(t\)，并假设每个顶点都在某条 \(s\leadsto v\leadsto t\) 路径上，因此 \(|E|\ge|V|-1\)。
流（flow）是函数 \(f:V\times V\to\mathbb R\)，满足：
- 容量约束（capacity constraint）：对所有 \(u,v\)，\(0\le f(u,v)\le c(u,v)\)；
- 流量守恒（flow conservation）：对所有 \(u\in V-\{s,t\}\)，\(\sum_{v}f(v,u)=\sum_{v}f(u,v)\)，即流入等于流出。
流守恒就是电路里的基尔霍夫电流定律：除源汇外，物料不在顶点积存。流的值（value）是
即流出源点的总量减去流入源点的总量（\(|\cdot|\) 在这里表示流值，不是绝对值）。通常没有进入源点的边，第二项为 0；保留它是因为后面在残存网络中会用到。最大流问题：给定 \(G,s,t\)，求值最大的流。
金融直觉：把顶点看作账户，\(f(u,v)\) 是今天从账户 \(u\) 划到账户 \(v\) 的金额。容量约束是"每条通道不超过当日额度，且不能划负数"；流量守恒是"中转账户（托管行、主经纪商）日终余额不变，进多少就出多少"。流值 \(|f|\) 是从资金来源净流出的总额，也等于最终到达交易所的总额。最大流问题就是"在所有合规的划转方案里，让到达交易所的总额最大"。
例（原书图 26.1，Lucky Puck 公司） 温哥华工厂（\(s\)）生产冰球，运往温尼伯仓库（\(t\)），途经埃德蒙顿（\(v_1\)）、卡尔加里（\(v_2\)）、萨斯卡通（\(v_3\)）、里贾纳（\(v_4\)）。每对城市间每天至多运 \(c(u,v)\) 箱：\(s\to v_1=16\)，\(s\to v_2=13\)，\(v_1\to v_3=12\)，\(v_2\to v_1=4\)，\(v_2\to v_4=14\)，\(v_3\to v_2=9\)，\(v_3\to t=20\)，\(v_4\to v_3=7\)，\(v_4\to t=4\)。原书图 (b) 给出一个值为 19 的流。公司关心的是每天能稳定运出多少箱，而不关心单个冰球花多久——稳态下中转城市不能积压，正对应流量守恒。
26.1.2 两个建模技巧
反平行边 如果又能租用埃德蒙顿到卡尔加里每天 10 箱的运力，网络中就同时有 \((v_1,v_2)\) 和 \((v_2,v_1)\)。处理办法是选其中一条，比如 \((v_1,v_2)\)，引入新顶点 \(v'\)，替换为 \((v_1,v')\) 和 \((v',v_2)\)，容量都是 10（原书图 26.2）。
多源多汇 \(m\) 个工厂 \(s_1,\dots,s_m\) 和 \(n\) 个仓库 \(t_1,\dots,t_n\)：加一个超级源点（supersource）\(s\)，连边 \((s,s_i)\) 容量 \(\infty\)；加一个超级汇点（supersink）\(t\)，连边 \((t_j,t)\) 容量 \(\infty\)（原书图 26.3）。若每个源恰好产出 \(p_i\)、每个汇恰好消耗 \(q_j\)，就把这些边的容量设为 \(p_i\)、\(q_j\)，再检查最大流是否把它们都填满（习题 26.2-6）。本章量化实战的资金调拨例子就用这一招。
还有一个常用技巧：顶点容量（习题 26.1-7）。若顶点 \(v\) 本身有通过上限 \(l(v)\)，把它拆成"入点"和"出点"，中间连一条容量 \(l(v)\) 的边。
26.2 Ford-Fulkerson 方法
称它为"方法"而不是"算法"，是因为它有多种实现，运行时间各不相同。它基于三个概念：残存网络、增广路径和割。
26.2.1 基本框架
FORD-FULKERSON-METHOD(G, s, t):
f ← 0
while 残存网络 G_f 中存在增广路径 p:
沿 p 增广 f
return f
从零流开始，每次在残存网络中找一条从 \(s\) 到 \(t\) 的路径，沿它增加流值，直到找不到为止。过程中单条边上的流可能减少——减少某些边上的流，可能是为了让更多的流到达汇点。
26.2.2 残存网络
给定流 \(f\)，残存容量（residual capacity）定义为
第一种情形是"还能再加多少"；第二种情形是"能退回多少"。例：\(c(u,v)=16\)，\(f(u,v)=11\)，则还能再加 \(c_f(u,v)=5\)，也能把最多 11 单位"退回"，\(c_f(v,u)=11\)。反向的残存边表示减少原边上的流。
白话解释：为什么需要"退回"？看一个最小的例子。边 \(s\to a\)、\(s\to b\)、\(a\to b\)、\(a\to t\)、\(b\to t\) 容量都是 1，最大流显然是 2（\(s\to a\to t\) 和 \(s\to b\to t\)）。但如果第一次运气不好，选了 \(s\to a\to b\to t\) 送 1 单位，那么 \(a\to b\)、\(b\to t\)、\(s\to a\) 都满了，只看原边就再也找不到路，卡在 1。 有了反向残存边，\(a\to b\) 上送出的 1 单位产生了一条 \(b\to a\) 的残存边（"可以把它退回"），于是出现新路径 \(s\to b\to a\to t\)。沿它送 1 单位，等于"撤销 \(a\to b\) 的那笔划转，让 \(s\to b\) 的钱直接去 \(t\)，让 \(a\) 的钱改走 \(a\to t\)"。结果两条原路径各 1 单位，总流 2。这就像发现划款指令排错了，不必推倒重来，只需追加一笔冲正。
残存网络 \(G_f=(V,E_f)\)，\(E_f=\{(u,v):c_f(u,v)>0\}\)。\(E_f\) 中的边要么是原边，要么是原边的反向，所以 \(|E_f|\le2|E|\)。
增广 若 \(f\) 是 \(G\) 中的流，\(f'\) 是 \(G_f\) 中的流，定义
在反向残存边上推流就是抵消（cancellation）：\(u\to v\) 送 5 箱、\(v\to u\) 送 2 箱，等价于 \(u\to v\) 送 3 箱。抵消是所有最大流算法的关键——没有它，贪心地选错一条路径之后就无法纠正。
引理 26.1 \(f\uparrow f'\) 是 \(G\) 中的流，且 \(|f\uparrow f'|=|f|+|f'|\)。
证明的要点是逐条验证：容量下界用 \(f'(v,u)\le c_f(v,u)=f(u,v)\)；容量上界用 \(f(u,v)+f'(u,v)\le f(u,v)+c_f(u,v)=c(u,v)\)；守恒性由 \(f\)、\(f'\) 各自守恒得出；流值把求和展开、重组即可。
26.2.3 增广路径
增广路径（augmenting path）是残存网络中从 \(s\) 到 \(t\) 的一条简单路径 \(p\)，它的残存容量是
沿 \(p\) 送 \(c_f(p)\) 单位的流（引理 26.2），新流值为 \(|f|+c_f(p)>|f|\)（推论 26.3）。路径上残存容量取最小值的那条边叫关键边（critical edge），增广后它从残存网络中消失。
26.2.4 割与最大流最小割定理
流网络的割（cut）\((S,T)\) 是 \(V\) 的一个划分，\(T=V-S\)，\(s\in S\)，\(t\in T\)。
- 穿过割的净流量：\(f(S,T)=\sum_{u\in S}\sum_{v\in T}f(u,v)-\sum_{u\in S}\sum_{v\in T}f(v,u)\)；
- 割的容量：\(c(S,T)=\sum_{u\in S}\sum_{v\in T}c(u,v)\)，只算 \(S\to T\) 方向。
定义的不对称是有意的。例（原书图 26.5）：\(S=\{s,v_1,v_2\}\)，\(T=\{v_3,v_4,t\}\)，值 19 的流穿过它的净流量是 \(f(v_1,v_3)+f(v_2,v_4)-f(v_3,v_2)=12+11-4=19\)，割的容量是 \(c(v_1,v_3)+c(v_2,v_4)=12+14=26\)。
白话解释：割就是在源和汇之间画一条"国境线"。净流量要算两个方向：出境减入境（这里 \(v_3\to v_2\) 的 4 单位是"回流"，要减掉）。容量却只算出境方向，因为它衡量的是"最多能往终点那边送多少"，而入境方向的管道对往外送没有帮助。正因为净流量可能被回流抵消、而容量不打折扣，才有"净流量 \(\le\) 容量"。
引理 26.4 对任意割，\(f(S,T)=|f|\)。（在 \(|f|\) 的定义上加上 \(S-\{s\}\) 中各顶点的守恒式——每个都等于 0——重组后 \(S\) 内部的项两两抵消，剩下 \(f(S,T)\)。）
推论 26.5（弱对偶） 任意流的值不超过任意割的容量：
定理 26.6（最大流最小割定理，max-flow min-cut theorem） 以下三条等价：
- \(f\) 是 \(G\) 的最大流；
- 残存网络 \(G_f\) 不含增广路径；
- 存在某个割 \((S,T)\) 使 \(|f|=c(S,T)\)。
证明：
- (1)⇒(2)：若有增广路径，由推论 26.3 可以严格增大流值，矛盾。
- (2)⇒(3)：令 \(S=\{v:G_f\text{ 中从 }s\text{ 可达 }v\}\)，\(T=V-S\)。\(t\) 不可达，所以这是一个割。对 \(u\in S,v\in T\)：若 \((u,v)\in E\)，必有 \(f(u,v)=c(u,v)\)，否则 \((u,v)\in E_f\)，\(v\) 就会在 \(S\) 中；若 \((v,u)\in E\)，必有 \(f(v,u)=0\)，否则 \(c_f(u,v)=f(v,u)>0\)。于是 \(f(S,T)=c(S,T)\)，再由引理 26.4，\(|f|=c(S,T)\)。
- (3)⇒(1)：由推论 26.5，\(|f|\le c(S,T)\) 对所有割成立；取等，说明 \(f\) 已达上界。\(\square\)
(2)⇒(3) 的证明本身就是一个算法：最大流求出后，在残存网络中从 \(s\) 做一次 BFS，能到达的顶点集合就是最小割的 \(S\) 侧，从 \(S\) 指向 \(T\) 的原边都是满载的"瓶颈"。量化实战中正是用这一点做瓶颈诊断。
这个定理的结构——"任意可行的最大化解 ≤ 任意可行的最小化解，并且两者最优值相等"——就是第 29 章的线性规划强对偶。最大流的对偶 LP 正是最小割（习题 29.4-3）。
推导拆解：把定理的三步翻成白话。 (1)⇒(2)：如果还能找到增广路径，就还能多送，那当前就不是最大，矛盾。 (2)⇒(3)：这一步最有内容。找不到增广路径时，把"从 \(s\) 出发、在残存网络里还走得到的顶点"圈成 \(S\)，其余为 \(T\)。跨越国境线的原边只有两种情况：从 \(S\) 出境的边必然已经满载（否则还有残存容量，对面的顶点就该被圈进 \(S\)）；从 \(T\) 入境的边上流量必然为 0（否则可以退回，产生一条 \(S\to T\) 的反向残存边）。于是"净流量 = 出境满载之和 − 0 = 割容量"。 (3)⇒(1)：弱对偶说任何流都不超过任何割；现在这个流恰好等于某个割，已经顶到天花板，不可能更大。 以 Lucky Puck 为例，最大流 23 时，割 \((\{s,v_1,v_2,v_4\},\{v_3,t\})\) 的三条出境边 \(v_1\to v_3\)、\(v_4\to v_3\)、\(v_4\to t\) 全部满载（\(12+7+4=23\)），而入境边 \(v_3\to v_2\) 上的流为 0。
26.2.5 基本 Ford-Fulkerson 算法与它的陷阱
def ford_fulkerson(G, s, t):
for (u, v) in G.E:
f[u, v] = 0
while (p := find_path_in_residual(G, f, s, t)) is not None: # DFS 或 BFS
cf_p = min(cf(u, v) for (u, v) in p)
for (u, v) in p:
if (u, v) in G.E:
f[u, v] += cf_p # 原边：加流
else:
f[v, u] -= cf_p # 反向边：抵消
return f
原书图 26.6 演示了它在图 26.1 网络上的运行，最终最大流值为 23。
分析：
- 容量为整数时，每轮流值至少加 1，循环至多 \(|f^*|\) 次；每次用 DFS/BFS 找路径 \(O(E)\)，总时间 \(O(E|f^*|)\)。有理数容量可以先放缩成整数。
- 容量为无理数时，选得不好的增广路径可能使算法不终止，流值甚至不收敛到最大值。
- 坏例子（原书图 26.7）：\(s\to u\)、\(s\to v\)、\(u\to t\)、\(v\to t\) 容量各 1,000,000，\(u\to v\) 容量 1。最大流 2,000,000。若交替选择 \(s\to u\to v\to t\) 和 \(s\to v\to u\to t\)（后者用了反向边），每次只能增加 1，需要两百万次增广。
白话解释：问题出在路径的"瓶颈"。\(s\to u\to v\to t\) 中间那根容量为 1 的细管决定了一次只能送 1。下一次走 \(s\to v\to u\to t\) 时，又只能把细管上的 1 单位退回来，同样只送 1。如此来回，流值每次只涨 1。运行时间 \(O(E|f^*|)\) 里的 \(|f^*|\) 指最大流的数值本身（这里是两百万），所以容量数字越大，最坏情况越慢；这与"图有多大"无关，是一个隐蔽的风险。Edmonds-Karp 优先走"步数最少"的路，绕开了细管，所以只需 2 次。
26.2.6 Edmonds-Karp 算法
改进很简单：用 BFS 找增广路径，即每次在残存网络中取边数最少的 \(s\to t\) 路径。时间 \(O(VE^2)\)，与容量大小无关。在上面的坏例子里，BFS 第一次就会找到两条边的路径，2 次增广就结束。
记 \(\delta_f(u,v)\) 为 \(G_f\) 中以边数计的最短距离。
引理 26.7 Edmonds-Karp 运行时，对所有 \(v\in V-\{s,t\}\)，\(\delta_f(s,v)\) 随每次增广单调不减。
证明思路：反设某次增广 \(f\to f'\) 使某些顶点的距离变小，取其中 \(\delta_{f'}(s,v)\) 最小的 \(v\)，设 \(G_{f'}\) 中最短路径的最后一条边为 \((u,v)\)，则 \(u\) 的距离没有变小。若 \((u,v)\in E_f\)，则 \(\delta_f(s,v)\le\delta_f(s,u)+1\le\delta_{f'}(s,u)+1=\delta_{f'}(s,v)\)，矛盾。若 \((u,v)\notin E_f\) 而在 \(E_{f'}\) 中，说明增广路径经过了 \((v,u)\)，而增广路径是最短路径，于是 \(\delta_f(s,v)=\delta_f(s,u)-1\le\delta_{f'}(s,v)-2\)，也矛盾。
定理 26.8 Edmonds-Karp 的增广总次数为 \(O(VE)\)。
证明思路：考察边 \((u,v)\) 两次成为关键边之间发生了什么。第一次时 \(\delta_f(s,v)=\delta_f(s,u)+1\)，增广后它从残存网络消失；要再出现，必须先有某次增广经过 \((v,u)\)，那时 \(\delta_{f'}(s,u)=\delta_{f'}(s,v)+1\ge\delta_f(s,v)+1=\delta_f(s,u)+2\)。所以 \(u\) 的距离每两次之间至少增加 2，而距离不超过 \(|V|-2\)，每条边至多成为关键边 \(O(V)\) 次。残存网络中可能出现的边有 \(O(E)\) 条，关键边总次数 \(O(VE)\)，每次增广至少一条关键边。\(\square\)
每次增广用 BFS \(O(E)\)，总时间 \(O(VE^2)\)。
白话解释：引理 26.7 与定理 26.8 的证明第一次读可以只抓住一句话：每次都走最短的增广路径，就保证每个顶点"离源点的步数"只增不减；而一条边每当再次成为瓶颈，它的起点离源点的步数至少要多 2。步数最多也就 \(|V|\) 左右，所以每条边当瓶颈的次数有限（约 \(|V|/2\) 次），总增广次数就被 \(|V|\times|E|\) 量级封顶，与容量数字大小无关。这就把上面"两百万次"的风险彻底消除了。
26.3 二分图最大匹配
26.3.1 问题
无向图中的匹配（matching）是边的子集 \(M\)，每个顶点至多与 \(M\) 中一条边关联。最大匹配是基数最大的匹配。二分图（bipartite graph）的顶点分为 \(L\)、\(R\) 两部分，所有边都在 \(L\) 与 \(R\) 之间。典型应用：\(L\) 是机器，\(R\) 是任务，边表示机器能做该任务，最大匹配让尽可能多的机器有活干。
26.3.2 归约为最大流
构造流网络 \(G'\)：加源点 \(s\) 和汇点 \(t\)；\(s\) 到每个 \(u\in L\) 一条边，每个 \(v\in R\) 到 \(t\) 一条边，原图的边改为从 \(L\) 指向 \(R\)；所有容量为 1。
引理 26.9 \(G\) 的匹配与 \(G'\) 中的整数值流一一对应，且 \(|M|=|f|\)。（每个 \(u\in L\) 只有一条容量 1 的入边，整数流下至多 1 单位流入，由守恒只能从一条边流出；\(R\) 侧对称。）
定理 26.10（整数性定理，integrality theorem） 若容量全为整数，Ford-Fulkerson 求出的最大流 \(f\) 中，\(|f|\) 和所有 \(f(u,v)\) 都是整数。（对迭代次数归纳：每次增广量是整数残存容量的最小值。）
推论 26.11 二分图最大匹配的基数等于对应流网络的最大流值。
匹配基数不超过 \(\min(|L|,|R|)=O(V)\)，所以 Ford-Fulkerson 用时 \(O(VE)\)。更快的 Hopcroft-Karp 算法 \(O(\sqrt VE)\) 见思考题 26-6。
整数性定理在量化里很重要：很多分配问题（订单分给通道、交易员分给品种）天然要求整数解，而流问题的线性规划松弛自动给出整数解，不必求解困难的整数规划。第 29 章会再提到这一点。
金融直觉：整数性定理的实用价值在于"免费拿到整数解"。比如把 300 笔委托分配到若干券商通道，每笔只能整体走一个通道。一般的整数规划很难求解，但只要问题能写成整数容量的流网络，算出来的最优流自动就是整数，即每笔委托恰好落在一个通道上，不会出现"0.4 笔走通道 A、0.6 笔走通道 B"这种无法执行的结果。
Hall 定理（习题 26.3-4）：\(|L|=|R|\) 时存在完美匹配，当且仅当对每个 \(A\subseteq L\)，\(|A|\le|N(A)|\)（\(N(A)\) 为 \(A\) 的邻居集合）。它可以由最大流最小割定理推出。
26.4 推送-重贴标签方法（选读）
原书 26.4、26.5 节是带 ★ 的选读内容。许多渐近最快的最大流算法以及最快的实际实现都基于这一方法。这里讲清思想和关键结论，细节可回原书。
26.4.1 与 Ford-Fulkerson 的区别
推送-重贴标签（push-relabel）更"局部"：不在整个残存网络中找路径，而是一次只处理一个顶点、只看它的邻居。它在执行中不保持流量守恒，只维护预流（preflow）——满足容量约束，且对 \(u\ne s\) 有"流入 ≥ 流出"。差额叫超额流（excess flow）\(e(u)=\sum_vf(v,u)-\sum_vf(u,v)\)；\(e(u)>0\) 的非源汇顶点称为溢出（overflowing）。
流体类比：每个顶点坐落在一个平台上，有一个蓄水池存放超额流。水只能往下坡推。源点高度固定为 \(|V|\)，汇点固定为 0。开始时把源点所有出边灌满；流进中间顶点后先存进蓄水池，再逐步往下推。若某个溢出顶点的所有未满出管都通向同高或更高的顶点，就把它抬高到"最低的、有未满管道相连的邻居高度 + 1"。最终能到达汇点的流都到了，剩下的超额流被抬过源点高度、送回源点。所有蓄水池清空时，预流就成了最大流。
26.4.2 两个基本操作
高度函数（height function）\(h\)：\(h(s)=|V|\)，\(h(t)=0\)，且对每条残存边 \((u,v)\)，\(h(u)\le h(v)+1\)。由此，高度差大于 1 的顶点之间没有残存边（引理 26.12）。
- PUSH\((u,v)\)：条件是 \(u\) 溢出、\(c_f(u,v)>0\)、\(h(u)=h(v)+1\)。推送 \(\min(e(u),c_f(u,v))\) 单位。推完后边满载的叫饱和推送，否则叫非饱和推送（推完 \(u\) 不再溢出）。
- RELABEL\((u)\)：条件是 \(u\) 溢出且所有残存出边都满足 \(h(u)\le h(v)\)。令 \(h(u)=1+\min\{h(v):(u,v)\in E_f\}\)。
通用算法：初始化预流后，只要有可执行的操作就任选一个执行。对任意溢出顶点，二者至少有一个可执行（引理 26.14）。
26.4.3 正确性与复杂度
- 正确性：算法始终维持 \(h\) 为高度函数（引理 26.16）。若 \(h\) 是高度函数，残存网络中就不存在 \(s\to t\) 路径——否则沿一条至多 \(|V|-1\) 条边的路径累加 \(h(v_i)\le h(v_{i+1})+1\)，得 \(|V|=h(s)\le h(t)+|V|-1\)，矛盾（引理 26.17）。终止时没有溢出顶点，预流是流；残存网络无增广路径，由最大流最小割定理，它是最大流（定理 26.18）。
- 高度上界：任何溢出顶点在残存网络中都有回到 \(s\) 的路径（溢出的流来自源点，可以原路退回），所以 \(h(u)\le2|V|-1\)（引理 26.19、26.20）。
- 操作计数：重贴标签少于 \(2|V|^2\) 次；饱和推送少于 \(2|V||E|\) 次；非饱和推送少于 \(4|V|^2(|V|+|E|)\) 次，用势函数 \(\Phi=\sum_{v:e(v)>0}h(v)\) 证明（第 17 章的势能法在这里派上用场）。总计 \(O(V^2E)\)（定理 26.24），优于 Edmonds-Karp 的 \(O(VE^2)\)。
26.4.4 前置重贴标签算法
精心安排操作顺序可以做到 \(O(V^3)\)。可容许边（admissible edge）是满足 \(c_f(u,v)>0\) 且 \(h(u)=h(v)+1\) 的边，它们构成的可容许网络是一个 DAG（引理 26.26）。算法维护一个顶点链表 \(L\)，从表头依次释放（DISCHARGE）溢出顶点——反复推送和重贴标签直到它没有超额；一旦某个顶点被重贴标签，就把它移到表头（算法名由此而来）。循环不变式是：\(L\) 始终是可容许网络的一个拓扑排序，且当前顶点之前的顶点都没有超额。
原书图 26.9、26.10 的例子：源点初始送出 26 单位，\(L=\langle x,y,z\rangle\)；依次释放 \(x\)、\(y\)、\(x\)、\(z\) 后，汇点收到 20 单位，\(s.e=-20\)，最大流为 20。
定理 26.30 前置重贴标签算法在任意流网络上运行时间为 \(O(V^3)\)。
实践中有两个关键启发式（注记中 Cherkassky 与 Goldberg 的结论）：定期在残存网络上做反向 BFS 重算精确高度（全局重贴标签），以及间隙启发式（gap heuristic，习题 26.5-5）——若某个高度 \(k\) 上没有任何顶点，高于 \(k\) 的顶点都不可能再把流送到汇点，可以直接抬到 \(|V|+1\) 以上。
26.5 思考题选讲
- 26-1 逃脱问题：\(n\times n\) 网格上给定 \(m\) 个起点，问能否找到 \(m\) 条顶点不相交的路径通往边界。拆点处理顶点容量，超级源连起点、边界点连超级汇，看最大流是否为 \(m\)。
- 26-2 最小路径覆盖：DAG 的最小路径覆盖数 \(=n-\) 最大匹配数。构造：每个顶点拆成 \(x_i\)、\(y_i\)，原边 \((i,j)\) 变成 \((x_i,y_j)\)，求二分图最大匹配。对有环图不适用（会得到环）。
- 26-3 项目选择（算法咨询公司）：\(n\) 个领域 \(A_k\)，雇专家费用 \(c_k\)；\(m\) 个项目 \(J_i\)，需要领域集合 \(R_i\)，收入 \(p_i\)；一个专家可同时参与多个项目。网络：\(s\to A_k\) 容量 \(c_k\)，\(J_i\to t\) 容量 \(p_i\)，\(A_k\to J_i\)（若 \(A_k\in R_i\)）容量 \(\infty\)。有限容量的割中，若 \(J_i\in T\)，则它需要的 \(A_k\) 都在 \(T\)（否则有一条无穷容量边穿过割）。于是最大净收入 \(=\sum p_i-\) 最小割容量，\(T\) 侧的项目就是要接的项目、\(T\) 侧的领域就是要雇的专家。这是经典的最大权闭包问题，量化实战中用它做策略上线选择。
- 26-4 更新最大流：整数容量下，某条边容量加 1，只需再找一次增广路径，\(O(V+E)\)；减 1 时，若该边满载，先沿一条经过它的流路径退回 1 单位，再尝试增广。适合"额度微调后重新评估"的场景。
- 26-5 容量缩放：\(C=\max c\)。\(K\) 从 \(2^{\lfloor\lg C\rfloor}\) 开始，每阶段只在残存容量 \(\ge K\) 的边上找增广路径，然后 \(K\) 减半。总时间 \(O(E^2\lg C)\)。
- 26-6 Hopcroft-Karp：每轮找一组极大的、顶点不相交的最短增广路径并同时翻转，至多 \(2\sqrt{|V|}\) 轮，总时间 \(O(\sqrt VE)\)，是二分图匹配的最佳已知算法。
26.6 量化实战
26.6.1 先核对原书例题
下面实现 Edmonds-Karp（返回流值、各边流量、最小割的 \(S\) 侧、增广次数）和一个简化的 FIFO 推送-重贴标签，在图 26.1 和图 26.7 上核对。
from collections import deque, defaultdict
def edmonds_karp(cap, s, t):
"""cap: dict[(u,v)] -> 容量。返回 (流值, 流 dict, 最小割的 S 侧, 增广次数)。"""
res = defaultdict(float); adj = defaultdict(dict) # dict 保持插入顺序，结果可复现
for (u, v), c in cap.items():
res[u, v] += c; adj[u][v] = adj[v][u] = None # 反向边初始残存容量 0
value, rounds = 0.0, 0
while True:
parent = {s: None}; q = deque([s])
while q and t not in parent: # BFS：边数最少的增广路径
u = q.popleft()
for v in adj[u]:
if v not in parent and res[u, v] > 1e-12:
parent[v] = u; q.append(v)
if t not in parent:
break
path, v = [], t
while parent[v] is not None:
path.append((parent[v], v)); v = parent[v]
cf = min(res[e] for e in path) # 残存容量 c_f(p)
for u, v in path:
res[u, v] -= cf; res[v, u] += cf # 反向残存边 = 可"抵消"的流
value += cf; rounds += 1
S = set(parent) # 最后一次 BFS 能到达的顶点
flow = {e: c - res[e] for e, c in cap.items()}
return value, flow, S, rounds
def push_relabel(cap, s, t):
"""简化的 FIFO 版推送-重贴标签（思路见习题 26.5-2），只返回最大流值。"""
V = {x for e in cap for x in e}; n = len(V)
res = defaultdict(float); adj = defaultdict(dict) # dict 保持插入顺序，结果可复现
for (u, v), c in cap.items():
res[u, v] += c; adj[u][v] = adj[v][u] = None
h = {v: 0 for v in V}; e = {v: 0.0 for v in V}; h[s] = n
active = deque()
for v in adj[s]: # INITIALIZE-PREFLOW：填满源点出边
d = res[s, v]
if d > 0:
res[s, v] -= d; res[v, s] += d; e[v] += d; e[s] -= d
if v != t: active.append(v)
while active:
u = active.popleft()
while e[u] > 1e-12: # DISCHARGE(u)
pushed = False
for v in adj[u]:
if res[u, v] > 1e-12 and h[u] == h[v] + 1: # 可容许边
d = min(e[u], res[u, v])
res[u, v] -= d; res[v, u] += d; e[u] -= d; e[v] += d
if v not in (s, t) and v not in active: active.append(v)
pushed = True
if e[u] <= 1e-12: break
if not pushed: # RELABEL(u)
h[u] = 1 + min(h[v] for v in adj[u] if res[u, v] > 1e-12)
return e[t]
# 图 26.1(a)：Lucky Puck 公司的运输网络
cap = {("s","v1"):16, ("s","v2"):13, ("v1","v3"):12, ("v2","v1"):4, ("v2","v4"):14,
("v3","v2"):9, ("v3","t"):20, ("v4","v3"):7, ("v4","t"):4}
val, flow, S, rounds = edmonds_karp(cap, "s", "t")
cut = [(u, v) for (u, v) in cap if u in S and v not in S]
print(f"Edmonds-Karp 最大流 = {val:.0f}，增广 {rounds} 次")
print("最小割 S =", sorted(S), " 割边", cut, " 容量", sum(cap[e] for e in cut))
print("推送-重贴标签 最大流 =", push_relabel(cap, "s", "t"))
# 图 26.7 的坏例子：边数最少的增广路径只需 2 次
bad = {("s","u"):10**6, ("s","v"):10**6, ("u","t"):10**6, ("v","t"):10**6, ("u","v"):1}
print("图26.7 Edmonds-Karp: 流值 %d，增广 %d 次" % edmonds_karp(bad, "s", "t")[::3])
输出：
Edmonds-Karp 最大流 = 23，增广 3 次
最小割 S = ['s', 'v1', 'v2', 'v4'] 割边 [('v1', 'v3'), ('v4', 'v3'), ('v4', 't')] 容量 23
推送-重贴标签 最大流 = 23.0
图26.7 Edmonds-Karp: 流值 2000000，增广 2 次
最大流 23 与原书一致；最小割 \((\{s,v_1,v_2,v_4\},\{v_3,t\})\) 的容量 \(12+7+4=23\) 恰好等于流值，这就是定理 26.6 的第 3 条。坏例子里 BFS 两次就结束，而不是两百万次。
注意两个实现细节：残存网络里每条原边都配了一条初始容量为 0 的反向边；邻接表用 dict 而不是 set，因为 Python 的字符串哈希每次运行都会随机化，用 set 会让 BFS 的访问顺序、进而让"多个最大流中选中哪一个"每次不同。
26.6.2 资金调拨：能否按时满足追加保证金
场景：某基金在两家银行有富余资金（银行 A 1.2 亿、银行 B 0.8 亿美元），今天收盘前需要向 CME、Eurex、HKEX 分别追加 1.0、0.6、0.4 亿保证金。资金只能经托管行、两家主经纪商划转，每条通道有当日额度。问：能否全部满足？若不能，瓶颈在哪？
这是一个多源多汇的最大流：超级源点到各银行的容量是富余资金，各交易所到超级汇点的容量是需求。若最大流等于总需求，就能满足（习题 26.2-6 的思路）。
import itertools
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import maximum_flow
# 此处沿用上一段代码中的 edmonds_karp
# ---------- 1. 资金调拨：能否在今天收盘前满足各交易所的追加保证金？ ----------
supply = {"银行A": 120, "银行B": 80} # 富余资金（百万美元）
demand = {"CME": 100, "Eurex": 60, "HKEX": 40} # 需追加的保证金
links = {("银行A", "托管行"): 70, ("银行A", "主经纪商1"): 50, ("银行B", "托管行"): 50,
("银行B", "主经纪商2"): 40, ("托管行", "主经纪商1"): 30, ("托管行", "主经纪商2"): 45,
("主经纪商1", "CME"): 80, ("主经纪商1", "Eurex"): 30, ("主经纪商2", "Eurex"): 35,
("主经纪商2", "HKEX"): 40, ("托管行", "CME"): 20} # 当日划转额度
cap = dict(links)
cap.update({("源", k): v for k, v in supply.items()}) # 多源多汇：超级源点、超级汇点
cap.update({(k, "汇"): v for k, v in demand.items()})
val, flow, S, _ = edmonds_karp(cap, "源", "汇")
print(f"可满足的保证金 {val:.0f} / 需求 {sum(demand.values())}")
print("未满足:", {k: v - flow[k, "汇"] for k, v in demand.items() if flow[k, "汇"] < v})
cut = [(u, v) for (u, v) in cap if u in S and v not in S]
print("瓶颈（最小割）:", cut, "容量", sum(cap[e] for e in cut))
# 用 scipy 交叉验证（要求整数容量）
nodes = sorted({x for e in cap for x in e}); ix = {v: i for i, v in enumerate(nodes)}
rows, cols, data = zip(*[(ix[u], ix[v], c) for (u, v), c in cap.items()])
G = csr_matrix((data, (rows, cols)), shape=(len(nodes), len(nodes)), dtype=np.int32)
print("scipy maximum_flow:", maximum_flow(G, ix["源"], ix["汇"]).flow_value)
cap[("托管行", "主经纪商1")] += 10 # 把瓶颈中的一条额度临时调高 10
print("托管行->主经纪商1 额度 +10 后:", edmonds_karp(cap, "源", "汇")[0])
输出：
可满足的保证金 175 / 需求 200
未满足: {'Eurex': 25.0}
瓶颈（最小割）: [('银行A', '主经纪商1'), ('托管行', '主经纪商1'), ('主经纪商2', 'Eurex'), ('主经纪商2', 'HKEX'), ('托管行', 'CME')] 容量 175
scipy maximum_flow: 175
托管行->主经纪商1 额度 +10 后: 185.0
读结果。总富余 2.0 亿，总需求 2.0 亿，表面上够用，但通道额度只允许送达 1.75 亿。最小割给出了为什么：所有资金最终都要经过"进入主经纪商 1 的两条通道（50+30）""主经纪商 2 流向交易所的两条通道（35+40）"和"托管行直达 CME 的通道（20）"，这五条通道合计 175，是不可逾越的上限。要提高能力，必须扩容这个割上的通道；扩容不在割上的通道（比如银行 A→托管行）毫无用处。把"托管行→主经纪商 1"提高 10 之后，可满足量升到 185。
两点提醒：
- "未满足"落在哪个交易所不是唯一的。最大流的值唯一，但流的分配可能有很多种；本次运行缺口落在 Eurex，换一种增广顺序可能落在 CME。如果各交易所的优先级不同（比如 CME 追保逾期的代价更高），应该用带费用的最小费用流（第 29 章 29.3.3 节把它写成 LP），给不同终点设不同的"未满足罚金"。
- 增量更新：额度调整后不必从头重算，思考题 26-4 说明整数容量下加 1 只需一次增广。
26.6.3 策略上线选择：项目选择问题
场景：一个量化团队考虑上线 6 个策略，每个策略有预期年收益，但依赖若干基础设施（Level2 行情、期权数据、海外托管、低延迟机房、另类数据），每项基础设施有年成本，且可以被多个策略共享。上线哪些策略、采购哪些设施，能使净收益最大？
直接枚举是 \(2^m\) 个子集，策略多了就不可行；思考题 26-3 说明它可以用一次最小割精确求解。
# ---------- 2. 策略上线选择（思考题 26-3 的项目选择 / 最小割） ----------
# 此处沿用 26.6.1 节代码中的 edmonds_karp 和上一段的 import itertools
infra = {"Level2行情": 40, "期权数据": 30, "海外托管": 50, "低延迟机房": 90, "另类数据": 60} # 年成本
strat = {"日内动量": (70, ["Level2行情", "低延迟机房"]),
"做市": (110, ["Level2行情", "低延迟机房"]),
"波动率套利": (65, ["期权数据"]),
"跨市场配对": (45, ["海外托管", "Level2行情"]),
"舆情因子": (50, ["另类数据"]),
"期权做市": (55, ["期权数据", "低延迟机房"])} # (年收益, 依赖)
INF = 1e9
cap = {("s", a): c for a, c in infra.items()}
cap.update({(j, "t"): p for j, (p, _) in strat.items()})
cap.update({(a, j): INF for j, (_, req) in strat.items() for a in req})
val, flow, S, _ = edmonds_karp(cap, "s", "t")
total_p = sum(p for p, _ in strat.values())
chosen = [j for j in strat if j not in S] # T 侧的策略 = 上线
hired = [a for a in infra if a not in S] # T 侧的基础设施 = 采购
print(f"最小割 {val:.0f}，最大净收益 = {total_p} - {val:.0f} = {total_p - val:.0f}")
print("上线策略:", chosen, " 采购:", hired)
best = max((sum(strat[j][0] for j in sub) - sum(infra[a] for a in {a for j in sub for a in strat[j][1]}), sub)
for r in range(len(strat) + 1) for sub in itertools.combinations(strat, r))
print("暴力枚举 2^6 个子集的最优净收益:", best[0], list(best[1]))
输出：
最小割 255，最大净收益 = 395 - 255 = 140
上线策略: ['日内动量', '做市', '波动率套利', '期权做市'] 采购: ['Level2行情', '期权数据', '低延迟机房']
暴力枚举 2^6 个子集的最优净收益: 140 ['日内动量', '做市', '波动率套利', '期权做市']
读结果。最优方案是上线日内动量、做市、波动率套利、期权做市四个策略，采购 Level2 行情、期权数据、低延迟机房，净收益 \((70+110+65+55)-(40+30+90)=140\)，与暴力枚举一致。"跨市场配对"单独看收益 45，但它独占的海外托管要 50，不划算；"舆情因子"收益 50 不够覆盖另类数据的 60。期权做市（55）单看不够付低延迟机房（90），但机房已经被日内动量和做市"摊薄"，加上它只需再付期权数据——而期权数据又被波动率套利共享。这种共享固定成本的组合效应正是贪心法容易出错、而最小割能精确处理的地方。
最小割的割值 255 也有含义：它等于"放弃的收益 + 付出的成本" \(=(45+50)+(40+30+90)=255\)。\(\sum p_i-\) 最小割 \(=\) 最大净收益。
推导拆解：为什么一次最小割就能解这个组合选择问题？关键是把每个割读成一个决策方案，并让割容量恰好等于该方案的"损失"。 第 1 步（割 = 决策）：策略在 \(T\) 侧表示"上线"，在 \(S\) 侧表示"不上线"；设施在 \(T\) 侧表示"采购"，在 \(S\) 侧表示"不采购"。 第 2 步（容量 = 损失）：被割断的边只有三类。\(s\to\) 设施被割断，说明该设施在 \(T\) 侧（采购了），计入其成本 \(c_k\)。策略 \(\to t\) 被割断，说明该策略在 \(S\) 侧（没上线），计入放弃的收益 \(p_i\)。设施 \(\to\) 策略的边容量为 \(\infty\)，若它被割断（设施在 \(S\)、策略在 \(T\)，即"上线了策略却没买它要的设施"），割容量就是无穷大，最小割绝不会选它。这就把"上线必须先采购依赖"这一约束自动编进了网络。 第 3 步（求和）：于是任何有限割的容量 \(=\) 放弃的收益 \(+\) 采购成本。净收益 \(=\) 上线收益 \(-\) 采购成本 \(=\sum p_i-\)（放弃的收益 \(+\) 采购成本）\(=\sum p_i-\) 割容量。让割容量最小，就是让净收益最大。
同一模型可以套用到很多量化场景：因子库里"上哪些因子、需要计算哪些中间数据"；多市场扩张时"进入哪些市场、需要哪些牌照和接入"。只要收益可加、成本按"用到就付一次"计，就是最大权闭包问题。
26.6.4 其他应用线索
- 订单分配：一批委托分给若干券商通道，每个通道有容量上限、每笔委托只能走支持该品种的通道，这是带容量的二分图匹配，即最大流。加上每条通道的费率，就成了最小费用流。
- 内部撮合（crossing）：内部的买单与卖单在价格兼容时可以对冲，最大化撮合量是一个二分图上的流问题。
- 系统性风险：银行间敞口网络中，最小割可用来找"切断后能隔离违约传染"的最小敞口集合。
本章小结
流网络由容量约束和流量守恒定义；流值等于穿过任意割的净流量，且不超过任意割的容量。最大流最小割定理把三件事等同起来：\(f\) 是最大流；残存网络无增广路径；存在割使流值等于割容量。残存网络中的反向边允许"抵消"已有的流，这是所有最大流算法的关键。Ford-Fulkerson 在整数容量下为 \(O(E|f^*|)\)；用 BFS 增广的 Edmonds-Karp 为 \(O(VE^2)\)，关键在于残存网络中的 BFS 距离单调不减。整数性定理保证整数容量下得到整数流，因此二分图最大匹配可以归约为最大流。推送-重贴标签维护预流和高度函数，只向下坡推送，通用版本 \(O(V^2E)\)，前置重贴标签 \(O(V^3)\)。建模上要会四个技巧：反平行边拆点、多源多汇加超级源汇、顶点容量拆点、项目选择化为最小割。量化中，最大流给出资金调拨能力的上限，最小割指出瓶颈；项目选择模型精确处理"共享固定成本"的组合选择。
| 概念 / 结论 | 公式或要点 |
|---|---|
| 流 | \(0\le f(u,v)\le c(u,v)\)；中间顶点流入 = 流出 |
| 流值 | \(\vert f\vert =\sum_vf(s,v)-\sum_vf(v,s)\) |
| 残存容量 | \(c_f(u,v)=c(u,v)-f(u,v)\)（原边），\(=f(v,u)\)（反向边） |
| 增广路径容量 | \(c_f(p)=\min_{(u,v)\in p}c_f(u,v)\) |
| 割 | \(f(S,T)=\vert f\vert \le c(S,T)=\sum_{u\in S,v\in T}c(u,v)\) |
| 最大流最小割 | 最大流值 = 最小割容量；\(S\) = 残存网络中 \(s\) 可达的顶点 |
| Ford-Fulkerson | \(O(E\vert f^*\vert )\)（整数容量） |
| Edmonds-Karp | BFS 增广，\(O(VE)\) 次增广，总 \(O(VE^2)\) |
| 整数性定理 | 整数容量 ⇒ 存在整数最大流 |
| 二分图匹配 | 单位容量网络的最大流，\(O(VE)\)；Hopcroft-Karp \(O(\sqrt VE)\) |
| 推送-重贴标签 | 预流 + 高度函数，\(O(V^2E)\)；前置重贴标签 \(O(V^3)\) |
| 项目选择 | 最大净收益 \(=\sum p_i-\) 最小割 |
练习
基础
- 在原书图 26.1(b) 的值 19 的流上，求割 \((\{s,v_2,v_4\},\{v_1,v_3,t\})\) 的净流量和容量。（原书 26.2-2。提示：注意反向边上的流要减去。）
- 在图 26.1(a) 上手工运行 Edmonds-Karp，写出每次的增广路径和残存容量。（原书 26.2-3。可用 26.6.1 的代码打印路径核对。）
- 把最大流问题写成线性规划。（原书 26.1-5。提示：变量为 \(f_{uv}\)，约束为容量和守恒，目标为流出源点的净流量；第 29 章式 (29.47)–(29.50)。）
- 顶点有容量 \(l(v)\) 时，如何把问题化为普通最大流？新网络有多少顶点和边？（原书 26.1-7。）
- 用最大流求无向图的边连通度（至少删掉多少条边才能使图不连通），至多需要多少次最大流计算？（原书 26.2-11。提示：固定一个顶点 \(s\)，对其余每个 \(t\) 求一次最大流，取最小值。）
进阶
- 证明 Hall 定理。（原书 26.3-4。提示：若对每个 \(A\) 都有 \(|A|\le|N(A)|\)，证明对应网络的最小割容量为 \(|L|\)。）
- 证明：最大流可以分解为至多 \(|E|\) 条路径上的流。（原书 26.2-10。）
- 在所有最小割中找边数最少的一个。（原书 26.2-13。提示：把容量改为 \(c'=c\cdot(|E|+1)+1\)。）
- 在 26.6.2 的资金调拨例子中，假设 CME 未满足的罚金是每百万 3 单位，Eurex 2 单位，HKEX 1 单位。把问题写成最小费用流（或 LP），用
scipy.optimize.linprog求解，看缺口如何分配。 - 在 26.6.3 的项目选择例子中，若"做市"策略的收益不确定，在什么区间内最优方案保持不变？（提示：对 \(p_{\text{做市}}\) 做参数扫描，每个值求一次最小割。）
原书推荐习题：26.1-5、26.1-7、26.2-4、26.2-10、26.2-11、26.3-4、26.4-4、26.5-5，思考题 26-3（强烈推荐）、26-5、26-6。
原书对照
页码换算：原书页码 = PDF 页码 − 21。
| 本章小节 | 原书章节 | PDF 页码（原书页码） |
|---|---|---|
| 导言 | 第 26 章导言 | p.729–730（708–709） |
| 26.1 流网络 | 26.1 Flow networks | p.730–735（709–714） |
| 26.2 Ford-Fulkerson 方法 | 26.2 The Ford-Fulkerson method | p.735–752（714–731） |
| 26.3 二分图最大匹配 | 26.3 Maximum bipartite matching | p.753–757（732–736） |
| 26.4 推送-重贴标签 | ★26.4 Push-relabel algorithms；★26.5 The relabel-to-front algorithm | p.757–781（736–760） |
| 26.5 思考题选讲 | Problems 26-1 ～ 26-6 | p.781–786（760–765） |
| — | Chapter notes | p.786–787（765–766） |