线性规划网络流 · 最大流、最小割与建模归约
一张带容量 capacity 的有向图,加上一个源 source 与一个汇 sink,问能从源送多少流量到汇——这就是 maximum flow。它看似只是一道图论题,却是组合优化里最通用的建模工具之一:调配、匹配、分割、取舍、带约束的可行性,大量问题都能翻译成网络流。本系列从最朴素的增广 (augment) 思想讲起,逐步把它打磨成高效算法,再翻到最小割与线性规划对偶的另一面,最后回到建模——把现实问题归约成网络流。
每页都把算法的执行过程预先展开成一串帧 (frame),每帧是一份完整快照(各边流量 + 高亮代码行 + 解说);页面只持有一个游标,前进 / 后退 / 自动播放都只是移动游标再重绘。选一张网、逐步推流,看 flow/cap 标签如何收紧、增广路与反向边如何出现、最小割如何从残量网络里浮现。
建议顺序:先把 求最大流的五种算法走一遍(增广路三种,再加距离标号与预流推进),再看 割与费用这两条对偶 / 加权的延伸,然后是 建模与归约的套路集,最后用 线性规划视角把前面所有结论统一起来。不确定自己缺什么数学的,先看 数学预备那页的依赖图——它按阅读目标标出哪几项前置真的用得上。
九项前置按会用 / 会建模 / 懂为什么三种阅读目标取舍,并按用途分四档,注明各项在哪一页兑现。可跳过, 读不下去时回来查。
网络流的数学预备
按会用、会建模、懂为什么三种目标把前置拆开：图论与摊还分析是底座，线性规划对偶与全幺模解释正确性，归约手法与势能法是手活。全幺模一节用可枚举的子式行列式给出整数解的证据。
前四页共用增广路框架,换的是「怎么找增广路」;末一页换范式,不找整条路,只推局部超额。
最大流与残量网络
从容量、守恒、流的值三条定义讲到 Ford-Fulkerson 增广框架，再到残量网络与反向边。单步跑朴素增广，看一条反向边如何撤销已占用的流量。
Edmonds-Karp:BFS 找最短增广路
Ford-Fulkerson 没规定怎么找增广路，DFS 任取在某些网上会很慢。Edmonds-Karp 只改一处：用 BFS 找边数最少的增广路，复杂度 O(VE²) 且与容量数值无关。
Dinic：分层图与阻塞流
每个相位先 BFS 建层次图，再一次 DFS 推出阻塞流，配合当前弧优化做到 O(V²E)。单步看相位二重分层后才用上的更长增广路。
ISAP：距离标号与就地重标号
Dinic 每个相位重建一次层次图。ISAP 把层号翻转成「到汇还有多远」的距离标号，全程只做一次反向 BFS，此后走不通就地抬高标号并只回退一步。gap 优化给出提前收工的判据：某个标号层被抬空，增广路就不可能存在。
HLPP：最高标号预流推进
Dinic 那页末尾的预流推进高度全取 0，靠 relabel 一格格垫出来。HLPP 补两处加速：反向 BFS 定初始高度，gap 把高度层抬空后够不到汇的点整批判死。搁浅网 40 步降到 11，而两者各自单独只降到 30 与 24。
它真实跑在哪里
最大流的另一面是最小割;给边加上费用就是最小费用最大流。
最大流最小割定理
把网络从最窄的咽喉剪断就是一个 s-t 割。从弱对偶到强对偶，给出三命题等价与构造证明，并从末态残量网络里直接读出最小割。
最小费用最大流
给每条边加上单位费用，在所有最大流里求总费用最小的那一个。主算法是 SSP：每次沿费用最短的增广路推流，因反向边带负费用而不能用 Dijkstra。
匹配、归约、带约束——网络流真正的威力在于建模。匹配这条线从无权走到带权, 最后走到归约失效的一般图。
二分图最大匹配
任务分派、招聘配对的内核。把二分图建成单位容量网络：最大流 = 最大匹配。增广路就是匈牙利算法的交替增广路。再串起 König 定理（最大匹配 = 最小点覆盖 = 最小割）与 Hall 婚配定理。
带权二分匹配：Kuhn–Munkres
每对配对带上权重后，目标从「配得多」变成「配得最划算」。KM 维护一组顶标，把搜索限制在相等子图里，卡住就按最小松弛量整体调标；同一实例归约成费用网络同样可解。
一般图最大匹配：blossom
奇环让「与根同奇偶」的划分自相矛盾，二分图那套交替搜索会漏掉真实存在的 augmenting path。Edmonds 把奇环整体缩成一个点修好了它，而展开由 parent 指针自动完成。
建模与归约：把问题翻译成网络流
多源多汇、点容量拆点、DAG 最小路径覆盖、最大权闭合子图四个套路，每个都讲清怎么建图、为什么对、答案怎么读，末尾附一张归约速查表。
上下界网络流
每条边除上界还有下界时，用 f = lower + g 拆解、以节点盈亏与超级源汇判定可行流；有源汇时加一条 t→s 的 ∞ 边化归为 circulation。
线性规划与对偶把整套理论收进一个框架。
线性规划视角：网络流是 LP，对偶即最小割
最大流本身就是一个 LP，其对偶恰是最小割，max-flow min-cut 即 LP 强对偶的特例。再看全幺模如何保证整数容量下 LP 最优自动取到整数流。
把反向边当作一种「撤销」的设计选择来读, 对照本站另外两个系列处理撤销的方式。
撤销与回溯：反向边的另一种读法
残量网络的反向边把撤销数据化了：撤销与前进用同一套原语表达，算法有 undo 却不需要 backtracking。对照 dancing-links 的回滚与 CRDT 的重放，并实测关掉反向边会损失多少。
相关链接
- 图论合集 · 最短路 / MST / 拓扑 本站 同一套「单步播放」骨架下的图算法。最短路里的 relaxation 与本系列的增广,是两种不同的「逐步收紧」。
- 稳定匹配 · Gale–Shapley 本站 另一种「匹配」目标:不是配对数最多,而是没有人想毁约。与二分图最大匹配那页恰成对照。
- Maximum flow problem en.wikipedia.org 最大流问题的标准定义、各类算法复杂度与应用索引。
- Max-flow min-cut theorem en.wikipedia.org 最大流最小割定理及其作为线性规划强对偶特例的解读。
- CP-Algorithms · 全站索引(含 Graph 一节) cp-algorithms.com 竞赛视角的算法索引,Graph 一节收了 Ford–Fulkerson / Edmonds–Karp、Dinic、MCMF、上下界流与各类建模套路的实现。