线性规划网络流 · 最大流、最小割与建模归约

一张带容量 capacity 的有向图,加上一个源 source 与一个汇 sink,问能从源送多少流量到汇 —— 这就是 maximum flow。它看似只是一道图论题,却是组合优化里最通用的建模工具之一:调配、匹配、分割、取舍、带约束的可行性,大量问题都能翻译成网络流。本系列从最朴素的增广 (augment) 思想讲起,逐步把它打磨成高效算法,再翻到最小割与线性规划对偶的另一面,最后回到建模 —— 把现实问题归约成网络流。

每页都把算法的执行过程预先展开成一串帧 (frame),每帧是一份完整快照(各边流量 + 高亮代码行 + 解说);页面只持有一个游标,前进 / 后退 / 自动播放都只是移动游标再重绘。选一张网、逐步推流,看 flow/cap 标签如何收紧、增广路与反向边如何出现、最小割如何从残量网络里浮现。

建议顺序:先把 求最大流的五种算法走一遍(增广路三种,再加距离标号与预流推进),再看 割与费用这两条对偶 / 加权的延伸,然后是 建模与归约的套路集,最后用 线性规划视角把前面所有结论统一起来。不确定自己缺什么数学的,先看 数学预备那页的依赖图 —— 它按阅读目标标出哪几项前置真的用得上。

预备:先备好的数学

九项前置按会用 / 会建模 / 懂为什么三种目标分档,注明各项在哪一页兑现。可跳过, 读不下去时回来查。

前置知识 · 分档取舍 · 依赖图

网络流的数学预备

按会用、会建模、懂为什么三种目标把前置拆开：图论与摊还分析是底座，线性规划对偶与全幺模解释正确性，归约手法与势能法是手活。全幺模一节用可枚举的子式行列式给出整数解的证据。

算法:最大流怎么算

前四页共用增广路框架,换的是「怎么找增广路」;末一页换范式,不找整条路,只推局部超额。

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

最大流与残量网络

全系列的地基。从容量 / 守恒 / 流的值三条定义，到 Ford-Fulkerson 增广框架，再到灵魂所在——残量网络与反向边。单步跑朴素增广，观察一条反向边如何撤销之前占用的流量，才能把流推到真正的最大。

Edmonds-Karp · BFS 最短增广路 · O(VE²)

Edmonds-Karp:BFS 找最短增广路

Ford-Fulkerson 没规定怎么找增广路；DFS 任取在某些网上会很慢。Edmonds-Karp 只改一处：用 BFS 找边数最少的增广路，复杂度 O(VE²)、与容量数值无关。一个下拉切换 BFS / DFS，并排对比两种策略的增广次数。

Dinic · 层次图 · 阻塞流

Dinic：分层图与阻塞流

不再每次 BFS 只换一条路。每个相位 (phase) 先 BFS 建层次图 (level graph)，再一次 DFS 推出阻塞流 (blocking flow)，配合当前弧优化做到 O(V²E)。单步看节点按层着色、相位二重分层后才用上的更长增广路。

ISAP · 距离标号 · gap 优化

ISAP：距离标号与就地重标号

Dinic 每个相位重建一次层次图。ISAP 把层号翻转成「到汇还有多远」的距离标号，全程只做一次反向 BFS，此后走不通就地抬高标号并只回退一步。gap 优化给出提前收工的判据：某个标号层被抬空，增广路就不可能存在。

HLPP · 最高标号 · 预流推进

HLPP：最高标号预流推进

Dinic 那页末尾的预流推进高度全取 0，靠 relabel 一格格垫出来。HLPP 补两处加速：反向 BFS 定初始高度，gap 把高度层抬空后够不到汇的点整批判死。搁浅网 40 步降到 11，而两者各自单独只降到 30 与 24。

它真实跑在哪里

调配与物流:供给 → 需求的最大 / 可行调配(带宽分配、电力潮流、运输问题)都是网络流骨架。 匹配与分派:任务指派、招聘配对、课程排表 = 二分图匹配;带成本的指派 = 最小费用流。 取舍与分割:计算机视觉的图像前景背景分割、project selection(最大收益项目选择)、网络可靠性,几乎都归约到最小割。 理论地位:网络流是「好解的线性规划」典范 —— 全幺模结构让连续优化自动给出整数解,这也是实务里要尽量把问题建模成网络流的原因。 对偶:割与费用

最大流的另一面是最小割;给边加上费用就是最小费用最大流。

最大流最小割定理 · 强对偶

最大流最小割定理

把网络从「最窄的咽喉」剪断，就是一个 s-t 割。从弱对偶（任意流 ≤ 任意割）到强对偶(max-flow = min-cut)，给出三命题等价与构造证明。单步跑完后，从末态残量网络里直接读出最小割：源侧 S 与割边一目了然。

最小费用最大流 · SSP

最小费用最大流

给每条边加上单位费用 cost：在所有最大流里求总费用最小的那一个。核心是 SSP——每次沿费用最短的增广路推流。看清为何残量网络的反向边带负费用、因而要用 SPFA / Bellman-Ford 而非 Dijkstra。

建模:把问题翻译成网络流

匹配、归约、带约束 —— 网络流真正的威力在于建模。

二分图匹配 · König / Hall

二分图最大匹配

任务分派、招聘配对的内核。把二分图建成单位容量网络：最大流 = 最大匹配。增广路就是匈牙利算法的交替增广路。再串起 König 定理（最大匹配 = 最小点覆盖 = 最小割）与 Hall 婚配定理。

建模与归约 · 拆点 · 路径覆盖

建模与归约：把问题翻译成网络流

网络流真正的威力在建模。多源多汇、点容量拆点、DAG 最小路径覆盖（= 点数 − 最大匹配）、最大权闭合子图 / project selection（= 正权和 − 最小割）…… 每个套路都讲清「怎么建图、为什么对、答案怎么读」，附一张归约速查表。

上下界网络流 · 可行流

上下界网络流

每条边除了上界还有下界 lower 时怎么办？用 f = lower + g 拆解、节点盈亏 + 超级源汇判定可行流；有源汇时加一条 t→ s 的 ∞ 边化归为无源汇 circulation。给一个完整的数值例子从头跑到尾。

收束:统一视角

线性规划与对偶把整套理论收进一个框架。

线性规划 · 对偶 · 全幺模

线性规划视角：网络流是 LP，对偶即最小割

系列收束之页，也是「线性规划网络流」的落点。最大流本身就是一个 LP，其对偶恰是最小割；max-flow min-cut = LP 强对偶的特例。再看全幺模 (total unimodularity) 如何保证整容量下 LP 最优自动取到整数最大流（整流定理）。

番外:横向对照

把反向边当作一种「撤销」的设计选择来读, 对照本站另外两个系列处理撤销的方式。

反向边 = undo · 不必回溯 · 归约

撤销与回溯：反向边的另一种读法

残量网络的反向边把撤销数据化了：撤销与前进用同一套原语表达，算法有 undo 却不需要 backtracking。对照 dancing-links 的回滚与 CRDT 的重放，并实测关掉反向边会损失多少。

相关链接

• 图论合集 · 最短路 / MST / 拓扑 本站 同一套「单步播放」骨架下的图算法。最短路里的 relaxation 与本系列的增广,是两种不同的「逐步收紧」。
• 稳定匹配 · Gale-Shapley 本站 另一种「匹配」目标:不是配对数最多,而是没有人想毁约。与二分图最大匹配那页恰成对照。
• Maximum flow problem en.wikipedia.org 最大流问题的标准定义、各类算法复杂度与应用索引。
• Max-flow min-cut theorem en.wikipedia.org 最大流最小割定理及其作为线性规划强对偶特例的解读。
• Maximum flow — CP-Algorithms cp-algorithms.com 竞赛视角的网络流实现合集:Edmonds-Karp、Dinic、MCMF、上下界流与各类建模套路。