最大流 · 残量网络 · 反向边

最大流与残量网络

一张流网络 (flow network) 就是带容量 capacity 的有向图：每条边 $u\to v$ 有一个上限 c(u,v)，有一个特殊的源 source s 与汇 sink t。最大流问题 (maximum flow) 问的是：从 s 到 t 最多能「输送」多少流量，使得每条边不超容量、每个中间点流入 = 流出？本页建立三块地基：流的定义、Ford-Fulkerson 增广框架，以及全系列的灵魂——残量网络与反向边。

1 · 流的定义：容量、守恒、流的值

一个流 (flow) 是给每条边赋一个数 f(u,v)，表示这条边上实际「跑」了多少流量。它必须满足两条约束：

容量约束 (capacity): 每条边的流量不超过其容量，且非负—— ${0 \le f(u,v) \le c(u,v)}$ 。

流量守恒 (conservation): 除源 s 与汇 t 外，每个点的总流入 = 总流出——流量在中间点既不凭空产生、也不凭空消失，像水管网络一样。

流的值 (value) |f|: 从源点净流出的总量（等价地，汇点净流入的总量）。最大流问题就是在所有合法流里，把这个 |f| 顶到最大。

直觉上，最大流会被某处「最窄的咽喉」卡住——这个咽喉就是最小割 (min-cut)，二者的深刻关系留到最大流最小割定理。本页先解决「怎么把流一点点推到最大」。

2 · 核心：残量网络与反向边

求最大流的朴素想法是增广 (augment)：在图里找一条从 s 到 t、沿途每条边都还没满的路，沿它尽量多推一点流，反复直到找不到这种路。这就是 Ford-Fulkerson 方法。但只在原图上找「没满的边」会走进死胡同——一条边一旦被某次贪心选择占满，就再也没法纠正，可能永远到不了真正的最大流。

残量网络 (residual network) 是解药。 给每条原边 $u\to v$ （容量 c、当前流量 f）在残量图里维护两条边：

正向残量边 $u\to v$ ，残量 = $c - f$ ——「还能再推多少」；
反向残量边 $v\to u$ ，残量 = f——「已经推了多少、因而可以撤销多少」。

增广路就在残量网络里找（只走残量 > 0 的边）。走一条正向边 = 多推流；走一条反向边 = 把之前推过的流退回去、给它改道的机会。

反向边为什么是对的？ 沿反向边 $v\to u$ 推 δ，等价于把原边 $u\to v$ 的流量减少 δ。这并不违反守恒：它在 u 处「少流出 δ」的同时，增广路在别处给 u 补上了 δ 的新流入；在 v 处「少流入 δ」也由增广路的后续边带走。最终每个中间点仍然流入 = 流出。反向边让算法能够撤销已用流量——这正是 Ford-Fulkerson 能保证求得全局最优的关键。

下面就用一张小网验证：朴素增广会先把中间边 $a\to b$ 占用，随后必须借一条反向边 $b\to a$ 把这部分流量退回、改道，才能达到真正的最大流 5。

注 · 反向边把「撤销」变成了一条边，这一步比它看起来更要紧。

撤销既然是图上的一条边，找路的代码就不必区分自己是在前进还是在回退——bfsAugment 与 pushFlow 对两种边一视同仁。算法因此有了撤销能力，却完全不需要回溯机制：没有操作日志、没有状态栈。撤销与回溯那页把反向边关掉实测了一遍，这张小网上流量会停在 4。

3 · 单步运行 Ford-Fulkerson

源 s、汇 t。每点「下一步」= 在残量网络里找一条增广路（这里用 DFS 任取一条）、算出沿途瓶颈残量、把这么多流量推上去。边标签是 flow/cap：绿色表示有流量、深色表示已占满。留意第三步会出现一条橙色反向边——那就是对已用流量的退回。

结束条件： 残量网络里再也找不到 $s\to t$ 的增广路。此时流值就是最大流。末态图里，从源点在残量网络中仍可达的点集 S（绿）与其余点 T（灰）之间的边（红）恰好构成一个割，其容量 = 最大流——这就是最大流最小割定理的预告。

接下来： Ford-Fulkerson 只说「找一条增广路」，没说怎么找。用 DFS 任取（如本页）在某些网络上会很慢；Edmonds-Karp 改用 BFS 找最短增广路，Dinic 再用分层图 + 阻塞流大幅加速；ISAP 把分层压到全程一次，HLPP 则换成不找整条路的预流推进。