4.1 流网络、流与残存网络

4.1 流网络、流与残存网络

本节摘要：流网络是每条边带容量上限的有向图，配有唯一的源点与汇点；一个合法的流必须同时满足容量约束（边流量不超过容量）与流量守恒（中间点进多少出多少）。本节定义这两个约束，重点拆解残存网络——把"每条边还能塞多少"画成一张新图，其中反向边代表"撤销已有流量的能力"，正是后续增广算法能够"反悔纠错"的机制来源。

阅读收获

阅读完本节，你应当能够：

1. 写出合法流的两个约束，并用它们校验给定的流；
2. 对一个具体的流逐边构造残存网络；
3. 解释反向边的语义（撤销通道）与它的容量算法；
4. 说明增广路径与瓶颈容量的定义，完成一次手工增广。

一、问题与直觉：管网里的两难

一个水库（源点）要向城市（汇点）供水，中间经过一张管道网，每段管道有粗细上限（容量）。问：这套系统每小时最多送多少水？

看似只要"每条管道都灌满"，但管网有分叉与汇合——上游灌得猛、下游管细，多余的水在中途节点无处可去。这暴露了流问题与前面所有章节的根本不同：它是一个带"守恒律"的分配问题。每个中间节点像一个泵站：进多少就必须出多少，一滴都不能凭空产生或消失；唯一"只进不出"的是源点，唯一"只出不进"的是汇点。

于是流网络的定义只有三件套：有向图、每条边一个非负容量、指定的源点 s 与汇点 t。流的"大小"定义为流出源点的净流量。

二、合法流：两条铁律

容量约束：每条边的流量不超过其容量。管道再想要水，也不能超过管径。

流量守恒：除源点与汇点外，每个顶点的流入量等于流出量。泵站不是水池。

示例网络：
A到B 容量16   A到C 容量13
B到C 容量10   B到D 容量12
C到B 容量4    C到D 容量20
D到C 容量9    C到T 容量4   D到T 容量20

一个合法的流可以为：
A到B 流12   A到C 流11
B到D 流7    B到C 流0
C到D 流11   ...
校验B：流入12 流出7加0等于12 守恒成立
校验容量：12不超过16 7不超过12 每边均满足
此时流出源点A共23 流入汇点T待算 应与23一致
​

这两条铁律同时是调试工具：写完最大流代码，拿最终结果逐边核对"流量不超容量、逐点进出平衡"，任何一条不满足，实现必有 bug。工程上建议把这个校验做成断言函数，比肉眼检查可靠得多。

三、残存网络：还能加多少的地图

给定网络 G 与流 f，残存网络回答的问题是："在当前流的基础上，每条边还有多少调整空间？"对每条边：

• 残存容量 = 容量减去当前流量。这是"顺向还能再塞多少"。
• 反向边：对每条有流量的边，补一条方向相反、容量等于当前流量的虚边——它是"撤销通道"，表示可以把已分配的流量收回来多少。

原始文集举过一个具体算例：某网络中 A 到 B 容量 16、当前流 12，则 A 到 B 残存容量为 4；同时因存在 12 单位的正向流，残存网络中出现 B 到 A 的反向边，残存容量 12。同理 B 到 C 有 7 单位流时，残存网络里多了 C 到 B 方向的 7——注意这个方向在原图中可能根本没有边，它是"账面上的撤销额度"。

反向边为什么必要？看一个经典困境：源点 s 经 a、b 两个中转到汇点 t，边为 s 到 a、s 到 b、a 到 b、a 到 t、b 到 t，容量都取 1。第一轮增广若走了"s 到 a、a 到 b、b 到 t"，用了中间的 a 到 b 边，a、b 之间被"堵死"。此后 s 到 a 到 t 与 s 到 b 到 t 两条路各只剩半程——没有反向边，算法就此卡死在流量 2；有了反向边，第二轮可走"s 到 b、b 经反向边到 a、a 到 t"，其中"b 到 a"一步实际是对先前 a 到 b 流量的撤销，最终得到正确的最大流 2……此处恰好仍为 2，但换个容量配置（s 到 a、a 到 t 等为更大值），有无反向边将直接决定能否达到真正的最大值。没有撤销机制的贪心分配会把自己锁死在局部最优——这是流问题与最短路径问题最深刻的差异。

四、增广路径与手工增广

增广路径：残存网络中从源点到汇点的一条简单路径。瓶颈容量：该路径上所有边残存容量的最小值——路径能增加的流量由最窄的一段决定。增广：沿路径把瓶颈量的流压进去，正向边残存容量减少、反向边残存容量等量增加，然后重画残存网络。

沿用原始文集的算例：残存网络中 A 到 C 为 2、C 到 D 为 5，路径 A 经 C 到 D 的瓶颈为 2，增广 2 单位后：A 到 C 残存归 0，同时新出现 C 到 A 与 D 到 C 两条反向边（各 2），C 到 D 残存降为 3。一次增广让残存网络"变形"一次——新反向边又可能开启此前不存在的新通路。

⚠️ 常见坑：残存网络里给"原图不存在的方向"也按对称补边。正确做法是：正向残存永远存在（哪怕容量为 0 时不必显式画出），反向边只在"该边当前流量大于 0"时有非零容量。另一个坑是增广时只改正向边忘了同步增加反向边容量，导致后续"反悔"通道失灵，算法提前卡死。

💡 关键直觉：把流想象成"已经签好的运输合同"，残存网络是"改合同的手续清单"——正向边是加订额度，反向边是退订额度。最大流算法的过程，就是不断用"加订加退订"的组合把总运量谈判到上限。

五、深入一层：为什么"反向边"是流问题的灵魂

反向边值得用更根本的语言再讲一遍。贪心算法的通病是"先做的决定锁死后面的选择"；最短路径问题里这个问题不存在（非负权下先定型的点不会被推翻），而流问题里它真实存在——早期的增广可能把容量用在了错误的位置。反向边的本质是给算法一个信用额度：允许它说"我之前把 7 单位流放在这条边上是个次优选择，现在退回来 3 单位"。数学上，残存网络把"正向剩余容量"与"反向可撤销量"放进同一个结构，增广路径于是可以自由地穿插"前进"与"回退"两种动作。

一个判定式的总结：凡是"分配型"问题（流、匹配、运输），几乎都需要某种反悔机制；凡是"排序型"问题（最短路、生成树），往往一个方向的贪心就够。面试里被问"最大流和最短路的本质区别"，这个视角比背复杂度更能体现理解深度。

残存网络的另一个细节：它随流实时变化，别把它当成静态结构缓存。每次增广后，路径上每条边的正反残存容量都要同步更新——这也是 4.3 节"成对边"实现存在的理由。

常见疑问解答

源点的"流出减流入"和汇点的"流入减流出"一定相等吗？

一定——把守恒约束对全部中间点求和，中间的边两两抵消，只剩源点的净流出与汇点的净流入。这个恒等式是校验实现的好工具：两边不等，说明守恒约束在某处被破坏。

残存容量会出现"负数"或"超过原容量"吗？

不会。正向残存等于容量减流量，流量在 0 与容量之间，残存也在 0 与容量之间；反向残存等于流量，同样非负且不超过容量。若代码里算出负残存，说明流本身已经违反容量约束，先查流的合法性。

增广路径为什么要"简单路径"（不重复经过点）？

非简单路径包含环，去掉环后路径仍连通源汇、瓶颈不小于原值——环只浪费容量。允许非简单路径不影响正确性但拖慢速度，所以定义上直接限定简单路径，实现上用 BFS/DFS 的 visited 天然保证。

一个流可以同时在一条边上"正着流"又"反着流"吗？

账面上会出现"正向流量加反向撤销"并存，但它们可以约掉——等效于一个更小的净流。实现时不必主动约简，算法自然处理；理解时把净流量当成真实状态即可。

动手实验：纸上的三轮增广

拿本节的示例网络（容量含 16、13、10、12、4、20、9）画三份残存网络草图，手工执行三轮增广：每轮先在残存网络上找一条源到汇的路，标注瓶颈，然后逐边更新正反残存容量，重画。第三轮结束后检查：是否出现了原图没有的反向边（一定会）；是否出现了"刚建的反向边又被用到"（大概率会）。这两个"一定会"就是本节的全部精髓——反向边不是可选装饰，而是增广生态的必需物种。画完三轮，你对 4.3 节代码里那两行"一减一加"的理解会完全不同。

流的合法性校验函数

写一个独立函数校验最终流：输入容量与流，逐边查"流量介于零与容量之间"，逐中间点查"流入等于流出"，最后比对"源净流出等于汇净流入"。三关全过返回真。这个三十行的函数是流算法最划算的测试资产——任何实现改动后跑一遍，比肉眼检查可靠一个数量级，也是面试白板编程时展示工程素养的加分细节。

要点串联

• 流网络三件套：有向图、边容量、唯一的源点与汇点。
• 合法流两铁律：流量不超容量（不爆管）；中间点进出相等（不积水）。两条都可以做成结果校验断言。
• 残存网络：每边"容量减流量"画出的调整空间地图，是增广类算法的工作现场。
• 反向边：容量等于当前正向流量的虚边，语义是"撤销已分配流量"，让算法具备纠错能力。
• 无反悔则锁死：贪心式的一次性分配会陷入局部最优，反向边是逃离的钥匙。
• 增广三步：找残存网络中源到汇路径；取瓶颈容量；沿路径调整并更新双向残存容量。
• 概念链条：容量守恒定义问题，残存网络定义空间，增广定义动作——下一节的定理为这一串动作收口。

反复增广什么时候该停？停的时候凭什么说"已经最大"？下一节的最大流最小割定理给出数学上的铁保证。