最大流 | Codeboy's Blog

形式陈述

容量网络以有限有向图为骨架，但允许平行弧与反平行弧。为保留这些情形，把 $A$ 看成有限的弧记录集合，每条记录 $a$ 有尾点 $\operatorname{tail}(a)$ 与头点 $\operatorname{head}(a)$ ；端点相同的两条记录仍是不同弧。另给不同的源点 $s,t\in V$ ，以及容量函数

c:A\to\mathbb R_{\ge0},

容量取值于非负实数。流是函数 $f:A\to\mathbb R_{\ge0}$ ，满足容量约束

0\le f(a)\le c(a)\qquad(a\in A)

以及每个 $x\notin\{s,t\}$ 上的守恒律

\sum_{a:\operatorname{head}(a)=x}f(a) = \sum_{a:\operatorname{tail}(a)=x}f(a).

流值是源点净流出

|f| =\sum_{a:\operatorname{tail}(a)=s}f(a) -\sum_{a:\operatorname{head}(a)=s}f(a).

最大流问题是在全部可行流中最大化 $|f|$ 。把所有顶点的净流出求和时，每条弧正负抵消，再代入中间点守恒，可得 $|f|$ 同时等于汇点净流入。零流总是可行；有限维可行域由闭的线性等式与区间 $0\le f(a)\le c(a)$ 构成且有界，所以非负实容量下最大值确实能达到。

残量记录

每条原弧 $a:u\to v$ 产生两条带原弧身份的残量记录：正向记录 $a^+:u\to v$ 的容量为 $c(a)-f(a)$ ，表示还能增加多少；反向记录 $a^-:v\to u$ 的容量为 $f(a)$ ，表示能撤销多少。只保留正残量记录便得到残量有向多重图。沿残量路经过 $a^+$ 时增加 $f(a)$ ，经过 $a^-$ 时减少 $f(a)$ 。

若原网络同时含反平行弧 $a:u\to v$ 与 $b:v\to u$ ，则 $a^-$ 和 $b^+$ 虽方向相同，仍有不同来源与更新规则。残量表示必须保留原弧 ID 及其正反配对索引，不能只按端点把两者合成一个数；否则一次撤销可能被错记成给另一条原弧加流。

直觉

容量限制每条有向通道能承载多少，中间顶点只转运、不生产也不消耗，目标是提高源到汇的净输送量。流不是一条路线：它可以在顶点处分叉与汇合，多条路线也会共享同一容量约束。

残量网络描述当前方案附近仍允许的改动。正向记录是尚未使用的余量，反向记录是撤销早先选择的权利；后者使算法能从局部不佳的路由中退回，而不必清空整张流重新开始。

流分解定理说明任意可行流都能拆成有限个源汇路径流与环流的非负组合。它为弧上的数值提供路线解释，却不要求最大流算法显式保存每个单位沿哪条路径移动；单商品流只区分总量，不追踪身份。

例子与边界

考虑容量

s\to a:3,\quad s\to b:2,\quad a\to b:1,\quad a\to t:2,\quad b\to t:3.

令 $f(s,a)=3,f(s,b)=2,f(a,t)=2,f(a,b)=1,f(b,t)=3$ ，中间点均守恒，流值为 $5$ 。源出弧总容量也是 $3+2=5$ ，因此任何流都不可能更大；这个同值流与割给出了可复算的最优证书。

平行弧可以分别承载流；若只关心最大值与顶点守恒，把同方向平行弧合并为容量之和不会改变最优值，但会丢失逐弧输出。反平行弧不能与残量反向记录混同。自环对净流量和守恒两侧贡献相同，可以删除而不改变最大流值。

容量只是上界，不要求每条弧用满；负容量让约束区间为空，标准模型不允许。所谓“无穷容量”在有限实现中应由问题结构证明出的有限上界代替；例如当源的所有出弧容量均有限时，它们的容量和就是流值上界。随意使用机器最大整数可能在加法中溢出。带下界、费用、顶点容量或多商品的流都改变可行域，需先给出相应归约或新模型。

推论与应用

最大流最小割定理把无残量增广路转成与流同值的割证书。Ford–Fulkerson 方法逐条选择增广路，任意实容量下的终止性取决于选路规则；Dinic 算法按残量距离分阶段求阻塞流，得到与流值无关的一般多项式界；Push–Relabel维护预流、超额与高度，按局部操作推进。算法复杂度必须注明 $|V|$ 、原弧记录数、容量类型与算术模型。

若所有容量为整数，存在每条弧流量也为整数的最大流。这是“存在整数最优解”，不是说任意使用浮点近似的实现会自动返回整数，也不把依赖最大流值的伪多项式迭代数变成输入位数的多项式。

带下界与需求的环流通过消去下界、计算顶点需求并加入超级源汇来检查可行性，不能直接把下界当残量。全局最小割使用无向图且不固定 $s,t$ ，虽可通过多次点对最小割联系，却不是一次固定源汇最大流的同一问题。多商品流还让多种商品竞争共享容量，需要新的变量与约束。

若若干源、汇只关心合计流量，可加入超级源和超级汇，并用各端点允许的供给、接收上界作为连接容量；若这些上界本身不存在，则要先从原网络推导安全有限界。该归约仍是单商品流，不能保留“某个源的单位必须送到某个指定汇”这类配对身份。

参考资料

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Ch. 24。
Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Ch. 7。
Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin, Network Flows, Prentice Hall, 1993，Chs. 4–7。

形式陈述 ​

残量记录 ​

反向链接

形式陈述

残量记录