沿一条通路增加流量，很容易得到比原来更好的方案。困难在于证明何时不能继续改善，以及早先选错的通路能否撤销。最大流的残量网络同时处理这两件事：正向残量表示还能增加多少，反向残量表示已有流量能撤回多少。

本篇固定使用Edmonds–Karp算法，每次用BFS找边数最少的增广路。它属于Ford-Fulkerson增广方法，但不能把任意选路规则的执行次数直接当作它的复杂度。最终输出除了流量，还包括一个容量相等的割，让最优性可以独立核对。

流的接口与可行性

输入n≥2个顶点、m条有向边、不同的源点s与汇点t。每条边有非负整数容量c，保留独立输入ID，允许平行边、相反方向的原始边和自环。输出每条原边的流f、总流值以及一个源侧顶点集合S。

可行流必须满足0≤f(e)≤c(e)。除s、t外，每个顶点的流入和流出相等。总流值取s的净流出，即流出减流入，而不是仅把源点所有出边相加；它同时等于t的净流入。

自环对净流量的贡献为零，教学实现不会利用它增广。零流总是可行，所以无需先解决一个寻找初始可行解的子问题。本篇没有下界流、多源供需或最小费用约束。

一条原边需要两个残量方向

原边u→v的当前流量为f时，正向残量是c−f，反向残量是f。沿正向增加Δ等于增加原边流量；沿反向增加Δ等于把原边流量减少Δ。两种操作都要求Δ不超过对应残量。

实现为每条输入边创建一对残量记录，编号为2i和2i+1，配对编号通过edge_id ^ 1取得。增广时把选中方向残量减Δ，配对方向加Δ。配对残量之和始终等于原容量，因此最后可用c减正向残量恢复原边流量。

如果原图本来同时含u→v和v→u，两条原边各有自己的一对记录，共四条残量记录。不能把后一条原边直接当作前一条的撤销记录，否则独立容量和独立流量会混在一起。平行边也按ID分别保留。

反向残量为何不可省略

考虑容量全部为1的边：

1
2
0→1, 0→2, 1→3, 1→4, 2→3, 3→5, 4→5
源0，汇5

若先走0→1→3→5，流值为1。只看原图尚有容量的正向边，第二条通路似乎被挡住了：1无法再从0取得流量，3也无法再向5送流量。

残量网络仍有0→2→3→1→4→5，其中3→1撤销了原边1→3上的流。增广后形成0→1→4→5与0→2→3→5两条单位流路径，总值为2。反向残量允许修改已有选择；它不表示原问题额外允许了一条原始通道。

增广保持容量与守恒

BFS只经过正残量边，得到一条从s到t的简单路径。取路径残量最小值Δ，并沿整条路径更新成对残量。容量条件由Δ的取法保持；每个内部顶点恰好增加同样多的净流入与净流出，所以守恒保持。源点净流出增加Δ，汇点净流入同样增加Δ。

从整数容量和零流出发，所有残量、瓶颈和流量都是整数。这能避免教学实现里的浮点容差问题。Edmonds–Karp的迭代次数证明本身不依赖容量大小，也不靠“每次至少增加1”建立；整数性不是该多项式界的必要条件。

没有增广路时，割给出上界

任取包含s、不包含t的集合S，把S中顶点的净流出相加。内部边一入一出抵消，留下跨出S的流减去跨入S的流，因此流值不超过跨出S的容量之和。这个不等式对每个可行流和每个s-t割都成立。

算法终止后，取正残量网络中从s可达的全部顶点作为S。t不在S中。每条从S跨出的原边必须满流，否则其正向残量会使终点也可达；每条跨入S的原边必须零流，否则其反向残量会使起点也可达。

于是流值恰好等于割容量：前者已经是可行方案，后者又限制所有可行方案。这证明当前流最大、当前割最小。证明依赖完整的可行流不变量；单独一句“搜索没有找到路径”不能替代容量与守恒检查。

BFS怎样限制增广次数

BFS按残量边数定义距离，容量大小不参与排序。增广后新增的残量方向只可能是本次路径上边的反方向。路径边u→v原来满足d(v)=d(u)+1；新增反边指向上一层，不能使任何顶点比原来更早到达。逐轮残量最短距离因而不下降。

一次增广至少使一条路径边残量变为零，称它为本次的一条关键边。若同一残量方向u→v再次成为关键边，中间必须有一次沿配对方向v→u增广，使它重新得到正残量。第一次有d(v)=d(u)+1；反向使用时有d新(u)=d新(v)+1。结合距离不下降，u的距离至少比第一次增加2。

仍可到达的顶点距离小于n，所以每个残量方向至多成为O(n)次关键边。共有2m个方向，增广次数为O(nm)。这限制的是BFS选最短增广路的版本，不是任意Ford–Fulkerson实现。

教学代码一次分配长度n的前驱与访问数组，后续用轮次时间戳标记访问，不每轮清空整个数组。一次BFS扫描至多2m条残量记录，访问O(m+1)个相关顶点；恢复路径和增广也在这个量级。包括初始化与最终失败搜索，总时间为O(n+m+nm²)，空间O(n+m)。m=0时仍须初始化并交付顶点相关结果，因此保留n项。

这是单位成本整数算术模型下的确定性最坏工作量；Python大整数操作还受位数影响。没有随机期望界，也没有用本机耗时证明复杂度。若每轮重新分配n长数组，应计入相应成本，不能不加条件照搬本实现的表达式。

独立证书检查与可复跑范围

教学实现examples/advanced-algorithms/max_flow.py返回流值、原边流数组、源侧割以及增广统计。从仓库根目录运行：

1
python3 examples/advanced-algorithms/check_max_flow.py

参照直接枚举包含s而不包含t的所有顶点子集，求最小割容量，不调用增广算法。另逐条检查容量、内部守恒、源汇净流量与返回割容量，避免把一个碰巧正确的数值当作正确流。

本次运行通过512个三顶点0/1容量图，对照1024个割；固定种子20260920的200个随机多重图，对照1220个割。另通过3个边界图和5个非法输入拒绝检查。上述撤销流样例得到值2，实际使用一次反向残量边，原边1→3最终流量为0。输出保存于examples/advanced-algorithms/results/max_flow.json。

枚举只用于小输入参照，不能扩展成一般图的有效求解器。证书等值提供当前输入的最优性依据，BFS距离与关键边论证提供一般终止和复杂度依据，两者的作用不同。

练习

  1. 对撤销流样例，分别列出第一次增广后原边1→3的两个残量值，以及第二次增广后的值。省略反边时具体丢失了哪个可行最优方案？
  2. 给定一个流数组与集合S，设计一个O(n+m)证书检查器。为什么只核对流值等于割容量，而不检查内部顶点守恒，会接受错误答案？

参考资料