给我一颗可以反悔的心

网络流：给我最大的水流，和一颗可以反悔的心

图：水从左侧源泉出发，经由容量不同的水道汇入城市；下方那条逆向的水路，暗示残量网络保留的“撤销权”。原创生成插画。

一座城市的水路已经修好：管道埋在地下，闸门钉在节点上，每条管道能承受多少水也早已写死。现在打开水源，问题看起来简单得近乎朴素：最多能有多少水抵达城市？

麻烦出现在第一股水拐弯之后。

一条眼前畅通的路，可能抢走后面更关键的管道；一处看起来已经塞满的瓶颈，也可能只是先前的调度姿势不对。如果我们每次都抓住一条能走的路，把水猛灌进去，最后得到的究竟是最大流，还是一个被自己堵住的局部死胡同？

网络流真正漂亮的地方，不只是“让水尽量多地流”。它还给算法装了一颗可以反悔的心。

先把水装进图里

一个流网络（flow network）由有向图 G = (V, E)、源点 s、汇点 t，以及每条边的容量 c(u,v) ≥ 0 组成。容量是管道的硬上限；流 f(u,v) 则是此刻真正经过它的量。

一个合法的流需要遵守两条自然法则。

容量限制（capacity constraint）

对每条边 (u,v)：

水不能倒着穿过一条不存在的管道，也不能把管道撑爆。

流量守恒（flow conservation）

对每个中间节点 v ∈ V \ {s,t}：

中间节点可以分流、合流，却不能在袖子里突然掏出三吨水，也不能悄悄喝掉两吨。

流的值 |f| 是源点的净流出量，也等于汇点的净流入量。在常见的简化模型里，没有边进入 s，也没有边离开 t，于是它就直接等于“从 s 出发的总流量”或“抵达 t 的总流量”。

这里要修正一个容易被定义藏起来的小地方：“源点入度为 0、汇点出度为 0”不是一般理论不可缺少的条件，而是很多课程采用的整洁约定。 即使原图不满足，也可以删去无助于最大流的流，或通过等价变换整理成这个样子。真正不能少的是容量约束与中间节点的流量守恒。

水路类比到这里很好用：

- 节点是分流与合流的位置； - 有向边是允许资源移动的方向； - 容量是局部限制； - 流量是一个同时满足所有限制的全局方案。

但水也只能陪我们走到这里。真实管网还有压力、时延、损耗和流体动力学；普通最大流模型默认资源可加、约束局部、经过中间点时守恒。类比负责开门，定义负责关门。

一条走得通，却走得不好的路

先看一个只有四个点的小网络。每条边容量都是 1：

我们第一次找到路径 s → a → b → t，于是送出 1 单位流。很合理，每条边都有容量，整条路都走得通。

然后算法抬头一看：s → a 满了，b → t 也满了。剩下的 s → b 和 a → t 明明各自畅通，却在方向上接不起来。若只允许继续向前加水，我们似乎只能停在 |f| = 1。

可这个网络明明能同时走两条路：s → a → t 与 s → b → t，总流量应该是 2。

问题不在管道，在旧选择。我们需要的不是另一条从零开始的路，而是一条能够一边前进、一边撤销 a → b 的路。

残量网络由此出现。

Residual graph：以变视之，万物流之

残量网络（residual graph）不记录“现在已经流了多少”，而记录“在当前方案上还能怎么改”。

设原图有一条 u → v，容量为 c，当前流量为 f。变化只有两类：

- 继续向前增加，最多还能加 c - f； - 把已经送出的水撤回来，最多能撤 f。

因此，原图里一条带有 f/c 的边，会在残量网络里变成：

残量容量为 0 的边可以不画。若原图本来就同时存在 u → v 与 v → u，实现时要把每条原始边各自维护成一对残量边，不能看见方向相反就把它们当成同一根管道。

图：4/7 的原边，向前还有 3 的余地，向后则保留 4 的撤销量。反向边不是现实中新修了一根倒流水管，而是对旧流量做减法的记账方式。

这就是整套方法的 hinge：反向边保存了撤销一次旧选择的权利。

重生之我在异世界拿下最大流 的标题虽然很长，机制倒很朴素。算法不必保证每一步都选对，只要错误仍然可以被写回去。

Augmenting path：能有活水源头来

残量网络中，从 s 到 t 的一条有向路径叫作增广路径（augmenting path）。路径上的每条残量边都代表一种合法改动：正向走是在原边上加流，反向走是在原边上减流。

一条增广路径最多能送多少？看路径上最小的残量容量，也就是瓶颈（bottleneck）：

Pretty straightforward——一串水管能通过多少水，不听最宽那根的豪言壮语，只听最窄那根的实话。

回到刚才那个四节点网络。第一次选择 s → a → b → t 后，残量网络中会出现反向边 b → a。于是第二条增广路径是：

其中 b → a 把先前 a → b 上的 1 单位流撤掉；另外两条边则各增加 1。算法没有把旧水硬挤过去，而是重新排了一次队。

图：粉色是第一次不理想的增广；青色是第二次在残量网络中的修正。最终 a → b 回到 0，两条更合适的路径各送 1。

可以在这里停一秒：如果删掉残量网络中的所有反向边，第二幅图还找得到从 s 到 t 的路吗？如果找不到，算法失去的就不只是一条边，而是纠正过去的能力。

Ford–Fulkerson：把“继续改”写成方法

Ford–Fulkerson（FF）更准确地说是一套 method，而不是把每个细节都钉死的单一算法。它规定不断寻找增广路径，却没有规定必须用 DFS、BFS，还是别的规则来找。

每轮更新都守住两个不变量：任何原边都不会超过容量；任何中间节点仍然流入多少、流出多少。与此同时，流值严格增加 Δ。

当容量都是整数时，每次增广至少增加 1，而总流量又有有限上界，所以过程一定终止，并且得到整数最大流。这条整数性很重要：如果流代表一件手办、一位顾客或一份工作，我们通常不想分到 0.37 个初音未来。

若每次用 DFS 在残量网络里随意找路，一次搜索通常是 O(E)，整数容量下最多增广 |f| 次，于是总复杂度为：

这里的 |f| 是最大流的值。这个界叫伪多项式（pseudo-polynomial）：容量 C 写进输入只需要 O(log C) 位，运行时间却可能跟 C 本身成正比。因此它可能相对于输入的比特长度呈指数级增长。说“容量大所以算法指数级”不够准确；真正的落差发生在“数值有多大”和“写下这个数要多少位”之间。

再补一条边界：对任意实数容量，随意选增广路径的 Ford–Fulkerson 甚至可能不终止。若总是用 BFS 选择边数最少的增广路径，就得到 Edmonds–Karp 算法，复杂度为 O(VE²)，不再依赖最大流数值。它未必是今天工程上最快的最大流算法，却把“选路运气”从复杂度里请了出去。

没有增广路，为什么就真的是最大？

“我已经找不到更好的了”和“世界上不存在更好的了”，中间隔着一份证明。

割（cut）把顶点分成两部分 (S,T)，要求 s ∈ S、t ∈ T。割的容量只计算从 S 指向 T 的原边容量：

而流过这个割的净流量，要用 S → T 的流减去 T → S 的流。由于中间节点内部的流入流出会相互抵消，穿过任何割的净流量都等于整个流的值 |f|。再由容量约束可得：

任何一条流都在尽力往上顶，任何一个割都在冷静地给它设上界。

现在假设 Ford–Fulkerson 已经停下。在最终残量网络里，把所有仍能从 s 到达的点放进 S，其余点放进 T。因为不存在增广路径，所以 t 必在 T。

这时发生两件事：

1. 每条原图中的 S → T 边都已饱和。否则它还会留下正的前向残量，把终点也带进 S。 2. 每条原图中的 T → S 边流量都为 0。否则它会产生一条从 S → T 的反向残量边，同样造成矛盾。

所以穿过这个割的净流量恰好等于割容量：

而我们早已知道，任何流都不可能超过任何割。当前流撞上了一个同样大小的上界，于是两边同时封顶：这个流是最大流，这个割是最小割。

图：两条跨割边都已饱和，割容量为 1 + 1 = 2，等于当前流值。最大流最小割定理在这里不是一句口号，而是一张可检查的最优性证书。

简而言之：max-flow 是尽力而为，min-cut 是物理极限。

我们之所以无法再多送一滴水，不是算法累了，而是某一道割上的容量已经把整个网络横着封住。

代码里的反向边：i ^ 1

竞赛实现里常把一条原边和它的反向残量边连续加入边数组：

若每一对都从偶数下标开始，那么相邻两条边可以用 i ^ 1 互相找到。与 1 异或会翻转二进制最低位：偶数变成相邻奇数，奇数变回相邻偶数。

这两行正好对应残量更新：当前方向少掉 Δ 的修改空间，反方向多出 Δ 的撤销空间。

但 i ^ 1 不是某种来自宇宙底层的网络流定律，它只在正反边连续存储，并且第一条边从偶数下标开始时成立。若数据结构的建边顺序不同，就老老实实存一个 rev 索引。硬件确实喜欢 XOR，但硬件不会替你检查数组有没有排好队。

“上帝视角”的周边调度

漫展开了一家初音未来周边快闪店。共有 k 种周边，第 j 种库存为 mj；门外有 n 位顾客，每个人只愿意购买清单里的商品。为了防黄牛，每人最多购买 5 件不同周边。怎样卖出最多件？

把限制直接焊进网络：

- s → 顾客 i，容量 5：每人最多拿五件； - 顾客 i → 周边 j，容量 1：只有想买才连边，同款每人至多一件； - 周边 j → t，容量 mj：总销量不能超过库存。

图：现实里的三类规则被分别放进三层边容量。拓扑负责“能不能买”，容量负责“最多买多少”。

为什么最大流恰好等于最多可售件数？这需要两个方向的对应：

- 任意一份合法销售方案，都能把每件售出的商品记作一单位 s → 顾客 → 周边 → t 的流； - 任意一份整数流，也能反过来读成销售方案：顾客—周边边上的 1 表示把那件商品交给那位顾客。

所有容量都是整数，因此存在整数最大流。于是网络不会给出“把一个吧唧切成 0.4 和 0.6 分给两个人”这种数学上丝滑、现实里会被赶出漫展的方案。

若所有顾客和周边的容量都为 1，这就是普通的二分图最大匹配；现在顾客容量为 5、商品一侧有库存，它更接近带容量的二分图匹配（b-matching / allocation）。二分图只是骨架，网络流则把两侧的配额也一起装了进去。

这种建模很强，但并非“一切现实法则都能直接降维成一条边”。单条容量最擅长表达可加的局部上限；若约束是“买 A 才能买 B”“A、B 只能二选一”“连续三天至少休一天”，通常还需要额外节点、时间展开、别的图模型，甚至整数规划。看到限制就画边是一种好直觉，知道什么时候一条边装不下，才算真正会建模。

The flow tells

回头看，网络流其实维护了四种彼此咬合的东西：

- 容量画出所有合法方案不能越过的边界； - 残量网络记录当前方案还能如何增加或撤销； - 增广路径给出一次可执行的改进； - 最小割在改进结束后，递上一张无法再优的证明。

它不要求我们第一次就选中完美路线。水可以拐错弯，可以退回来，可以换一条路；只要残量网络仍诚实地记着每一次增加与撤销，局部的选择就不会被永久写死。

最优解不是凭直觉“看”出来的。我们划好容量，连好拓扑，让水流过，再由那道最窄的割告诉我们：到这里，一滴也不能更多。

Be water, my friend.