最小费用最大流 · SSP

最小费用最大流

前面各页只关心一个问题：流能有多大。但现实里，把同样多的流量送到汇点，往往有许多种不同的走法——走 A 通路和走 B 通路，流值一样，代价却天差地别。给每条边再加一个单位费用 cost：每送一单位流量经过它，就要付出 cost(e) 的代价。在所有最大流当中，挑出总费用最小的那一个，就是最小费用最大流 (minimum-cost maximum-flow, MCMF)。

1 · 模型：容量加费用，两层目标

在最大流的基础上，给每条边 $u\to v$ 再附一个非负的单位费用 cost(u,v)。于是每条边带两个参数 (cap, cost):cap 限制它最多能跑多少，cost 决定每跑一单位要花多少钱。一个流 f 的总费用定义为各边流量乘以单位费用之和：

总费用 (total cost): $cost(f) = Σ_e f(e) \cdot cost(e)$ ——对每条边，实际流量 × 单位费用，再求和。

两层目标 (lexicographic): 先把流值 |f| 顶到最大（最大流的目标不变）,再在所有「流值 = 最大流」的合法流里，把上面这个 cost(f) 压到最小。这是一个字典序目标：流量优先，费用次之。

之所以是「先最大、再最便宜」，是因为最大流问题本身先确定了要送多少货；MCMF 在此前提下回答怎么送最省钱。也存在另一类问题只求「在预算内送尽量多」或「送固定量求最省」——它们都是同一套费用流框架的变体，本页聚焦最常见的「最大流 + 最小费用」。

它和纯最大流的关系。 把所有边的 cost 都设为 0,MCMF 就退化成普通最大流——任何最大流的费用都是 0，没有优劣之分。一旦费用各异，**「走哪条路」**就有了讲究：同样推一单位到 t，绕远的廉价通路可能比抄近的昂贵通路更划算。

2 · SSP：把「最短」换成「最便宜」

回忆 Edmonds-Karp：它每次在残量网络里找一条边数最少的增广路。连续最短路 (successive shortest paths, SSP) 求 MCMF 的思路，只改动一处——把「最短」的度量从边数最少换成单位费用之和最小。其余完全照搬增广框架：

SSP 主循环：

在残量网络里找一条从 s 到 t 的费用最短增广路 P（路上各边 cost 之和最小，只走残量 > 0 的边）;
求出 P 的瓶颈残量 δ，沿 P 推流 δ;
这一步增加的费用 = δ ×（P 的单位费用）；累加进总流量与总费用；
重复，直到残量网络里再无 $s\to t$ 路——此时即 MCMF。

为什么「每次走最便宜的」就对？ 可以证明一条不变量 (invariant)：只要每一步都沿费用最短增广路推流，那么每推完一步，得到的流都是**「当前这个流值下，费用最小的流」。这是归纳的结果——初始零流显然最优；若推流前是当前流值的最优解，沿费用最短路增广 δ 后，新流仍是新流值的最优解（任何更便宜的同流值流都意味着残量网络里存在负费用环**，与归纳前提矛盾）。因此循环到无增广路为止，既达到了最大流值，又在该流值下费用最小。

与最大流里「BFS 找最短路」相比，这里把无权图上的 BFS 换成了带权图上的最短路算法。而残量网络的权恰恰可能为负，这就引出了下一节的关键选择。

3 · 关键：为什么用 SPFA / Bellman-Ford，不用 Dijkstra

残量网络里的反向边（最大流与残量网络的核心）在费用流里有了新含义：正向边 $u\to v$ 费用为 +cost；它的反向边 $v\to u$ 费用为 $-cost$ 。原因很自然——沿反向边推流 = 撤销之前在正向边上推的流，既然当初付了 cost，撤销时就该退回 cost，于是反向边的费用是负数。

负权边 → Dijkstra 失效。 Dijkstra 求最短路的正确性依赖所有边权非负：它一旦确定某点的最短距离就不再回头。残量网络里反向边的负费用会破坏这个前提——一条后来出现的负权边可能让某个「已敲定」的点其实还能更便宜地到达，Dijkstra 直接用会给出错误的费用最短路。

所以朴素 SSP 用能处理负权边的最短路算法：Bellman-Ford，或它的队列优化版 SPFA (shortest path faster algorithm)。SPFA 用一个队列只重新松弛「距离刚被更新」的点，实践中通常比逐轮全量松弛的 Bellman-Ford 快，本页引擎即用 SPFA 找每一步的费用最短增广路。

提速：Johnson 势函数 (potential)。 每轮都跑 Bellman-Ford / SPFA 较慢（单次 $O(V\cdot E)$ ）。一个标准优化是给每个点维护一个势 (potential) h(v)，把边 $u\to v$ 的费用改写成归约费用 (reduced cost) $cost(u,v) + h(u) - h(v)$ 。只要 h 取得当（初始用一次 Bellman-Ford，之后每轮用上一轮的最短距离更新），归约费用恒为非负，于是每一轮都能改用 Dijkstra（配堆 $O(E\cdot \log V)$ ），而最短路的相对顺序不变。这就是 Johnson 算法用在费用流上的形态。

4 · 单步运行 MCMF

下面这张费用网每条边标 flow/cap $cost。源 s、汇 t，最大流为 4。每点「下一步」= 用 SPFA 找一条单位费用最小的增广路、推满它的瓶颈。留意 MCMF 先挑便宜的通路走满，迫不得已才动用更贵的边——最终在流值 4 下，总费用被压到最小 14。

读懂这两步。 第一次增广走的是更便宜的那条通路（本网里经 b，单位费用 3），把它的瓶颈推满；第二次才退而走单位费用更高的通路（经 a，单位费用 4）。两步的顺序由 SPFA 自动决定——它每次都返回当下最便宜的增广路。最终流值 4、费用 14，正是「最大流之中费用最小」的那一个流。

复杂度。 朴素 SSP 的每次增广要跑一遍 SPFA/Bellman-Ford( $O(V\cdot E)$ )；增广次数最多 $O(V\cdot E)$ （整数容量下每次至少推满一条边），故朴素上界约 $O(V\cdot E^2)$ 。配合 Johnson 势函数后每轮改用 Dijkstra，可降到 $O(f \cdot E\cdot \log V)$ 量级（f 为最大流值或增广次数），是实际工程实现的常见做法。

5 · 它真实跑在哪里

费用流是运筹学里被研究得最透的模型之一，大量「带成本的资源调配」问题都能直接化归为它：

运输问题 (transportation): 若干仓库（供给）向若干门店（需求）发货，每条「仓库→门店」线路有运量上限与单位运费。求满足需求且总运费最小的调运方案 = 一个标准的最小费用流。

指派问题 (assignment): n 个工人分派给 n 项任务，工人 i 做任务 j 的成本为 c(i,j)，每人一任务、每任务一人，求总成本最小的指派。它正是带权二分图完美匹配——建成单位容量、边带费用的网络，MCMF 一次解出（详见二分图匹配）。

带成本的调度 (scheduling): 任务在机器/时间槽间分配，每种分配方式代价不同且有容量约束；把时间、机器建成节点，用费用流求最小代价的可行调度。

网络设计 (network design): 通信/电力网中，在满足流量需求的前提下，用费用流求最省成本的路由或扩容方案。

承上启下。 指派问题把「费用」加到了二分图匹配上——而无权的二分图最大匹配，本身就是单位容量最大流的一个简洁特例。二分图最大匹配那页就从这个角度，把匹配问题完整地建成流网络来求解。