图论中的最小费用最大流问题（Capacity Scaling 算法）
今天我们来讲解最小费用最大流问题（Minimum Cost Maximum Flow, MCMF）中一种经典的优化算法——Capacity Scaling 算法。它是在 Successive Shortest Path (SSP) 方法的基础上，通过引入“容量缩放”的思想来减少寻找最短增广路径的次数，从而提升算法的效率。
1. 问题描述
我们有一个带权有向图 \(G = (V, E)\)，其中每条边 \((u, v) \in E\) 有两个属性：
- 容量 \(c(u, v) > 0\)，表示该边能承载的最大流量。
- 单位费用 \(w(u, v)\)，表示通过该边单位流量所需支付的费用。
此外，我们有两个特殊顶点：
- 源点 \(s\)：流量从该点发出。
- 汇点 \(t\)：流量最终流向该点。
目标：
在满足所有边容量限制和流量守恒（除 \(s\) 和 \(t\) 外，流入等于流出）的前提下，找到从 \(s\) 到 \(t\) 的最大流 \(F_{\max}\)，并使得总费用 \(\sum_{(u,v) \in E} w(u,v) \cdot f(u,v)\) 最小（其中 \(f(u,v)\) 是边上的实际流量）。
2. 基础背景：Successive Shortest Path (SSP) 算法
Capacity Scaling 算法建立在 SSP 算法之上。我们先简要回顾 SSP 的基本步骤：
- 初始化：流量 \(f = 0\)，残量网络 \(G_f\) 与原图相同。
- 在残量网络 \(G_f\) 中，以费用为边权，寻找从 \(s\) 到 \(t\) 的一条最短路径（即总费用最小的路径）。
- 沿着该路径尽可能多地推送流量（受路径上最小残存容量限制）。
- 更新残量网络（添加反向边，并更新边上的残存容量）。
- 重复步骤 2-4，直到无法再找到从 \(s\) 到 \(t\) 的路径为止。
SSP 算法的每次迭代都需要跑一次最短路径算法（如 Bellman-Ford 或 Dijkstra 结合势能函数）。在最坏情况下，迭代次数等于最大流值 \(F_{\max}\)（每次推送至少 1 单位流量）。
3. Capacity Scaling 的核心思想
关键洞察：
与其每次只推送 1 单位流量，不如尽量多地推送。但如何决定“多”是多少呢？
Capacity Scaling 的做法是：
- 设所有边容量的最大值为 \(C_{\max}\)。
- 我们从一个较大的“容量阈值” \(\Delta\) 开始（通常初始化为不小于 \(C_{\max}\) 的最大的 2 的幂）。
- 在每次“缩放阶段”中，我们只考虑残量网络中容量至少为 \(\Delta\) 的边，并在这个子图上寻找最短增广路径、推送尽可能多的流量（但至少推送 \(\Delta\) 单位）。
- 当无法再推送流量时，将 \(\Delta\) 减半，进入下一个缩放阶段。
- 重复直到 \(\Delta = 0\)。
这样，我们优先利用“宽”的边来输送大量流量，从而减少需要寻找最短路径的次数。
4. 算法步骤详解
以下为 Capacity Scaling 算法（与势能函数结合，使用 Dijkstra 找最短路径）的完整步骤。
步骤 1：初始化
- 初始流量 \(f(u,v) = 0\) 对所有边。
- 计算初始 \(\Delta = 2^{\lfloor \log_2 C_{\max} \rfloor}\)（即最大容量的最高 2 的幂）。
- 初始化势能函数 \(\pi(v) = 0\) 对所有顶点 \(v \in V\)（用于将边权转换为非负，以便使用 Dijkstra）。
步骤 2：主循环（缩放阶段）
只要 \(\Delta \geq 1\) 就重复：
阶段内循环：
-
构建“\(\Delta\)-残量网络” \(G_f(\Delta)\)：包含所有满足 残存容量 \(r(u,v) \geq \Delta\) 的边 \((u,v)\)（包括正向边和反向边）。
- 残存容量 \(r(u,v) = c(u,v) - f(u,v) + f(v,u)\)（注意反向边的贡献）。
- 边 \((u,v)\) 在 \(G_f(\Delta)\) 中的权重为修正费用 \(w_{\pi}(u,v) = w(u,v) + \pi(u) - \pi(v)\)。
这是Johnson势能技巧，保证在 \(G_f(\Delta)\) 中所有边权重非负（只要初始势能设置正确且每次更新后维持性质），从而可用 Dijkstra 算法。
-
在 \(G_f(\Delta)\) 上运行 Dijkstra 算法，寻找从源点 \(s\) 到汇点 \(t\) 的最短路径（按修正费用 \(w_{\pi}\)）。
-
如果存在这样的路径 \(P\)：
- 计算路径上的最小残存容量 \(\text{minRes} = \min_{(u,v) \in P} r(u,v)\)。
- 由于 \(P\) 在 \(G_f(\Delta)\) 中，所以 \(\text{minRes} \geq \Delta\)。
- 我们沿路径 \(P\) 推送 \(\text{minRes}\) 单位的流量（可以大于 \(\Delta\)，因为路径上可能有多余容量）。
- 更新流量 \(f\) 和残量网络。
- 更新势能：对于所有顶点 \(v\)，设置 \(\pi(v) = \pi(v) + d(v)\)，其中 \(d(v)\) 是 Dijkstra 中计算出的从 \(s\) 到 \(v\) 的最短距离（按 \(w_{\pi}\)）。
这一步保证下一轮迭代中，修正费用依然非负。
- 重复阶段内循环（继续在同一个 \(\Delta\) 下寻找下一条路径）。
-
如果不存在从 \(s\) 到 \(t\) 的路径，则跳出当前阶段内循环。
阶段结束：
- 将 \(\Delta\) 除以 2（或右移一位：\(\Delta \leftarrow \Delta / 2\)）。
- 进入下一个缩放阶段。
步骤 3：终止
当 \(\Delta = 0\) 时，算法结束。此时我们得到了最小费用最大流。
5. 算法正确性说明
为什么这样做是对的？
- 完整性：当 \(\Delta = 1\) 时，\(G_f(1)\) 就是普通的残量网络。因此最后一轮缩放阶段等价于标准的 SSP 算法，最终会得到最大流。
- 费用最小性：每个缩放阶段中，我们都是在当前 \(\Delta\)-残量网络上寻找最短路径（按修正费用），并沿最短路径增广。这与 SSP 算法相同，而 SSP 算法（在无负环且使用势能时）保证得到的流是最小费用的。
- 非负权保证：势能函数 \(\pi\) 的更新确保了在缩放阶段内每次 Dijkstra 都在非负权图上运行，这是正确的关键。
6. 时间复杂度分析
设 \(n = |V|\)，\(m = |E|\)，最大容量值为 \(C_{\max}\)，最大流值为 \(F_{\max}\)。
- 缩放阶段数：\(O(\log C_{\max})\)。
- 在每个缩放阶段 \(\Delta\) 内，每推送至少 \(\Delta\) 单位的流量。因此，每个缩放阶段最多进行 \(O(F_{\max} / \Delta)\) 次增广。
- 每次增广需要一次 Dijkstra（\(O(m + n \log n)\) 或 \(O(n^2)\)，取决于实现）。
总和起来，总增广次数为 \(O(\log C_{\max} \cdot F_{\max})\)，但实际上因为早期 \(\Delta\) 较大时每次推送流量多，实际运行比 SSP（增广 \(O(F_{\max})\) 次）更快，尤其在容量值较大时。
7. 示例演示
考虑一个简单网络（数字为（容量，费用））：
(2,2)
s ------> v1
| \ |
(1,1)(3,1)| (1,3)
| \ |
V \ V
v2 ----> t
(2,1)
初始 \(C_{\max} = 3\)，所以 \(\Delta = 2\)。
-
阶段 Δ=2：
- 残量网络中容量 ≥2 的边：\(s \to v1\)（残量 2）、\(v2 \to t\)（残量 2）等，但 \(s \to v1 \to t\) 不存在，其他路径容量不足 2。因此本阶段无增广。
-
阶段 Δ=1：
- 考虑所有残量 ≥1 的边。
- 增广 1：路径 \(s \to v2 \to t\)，流量 1，费用 1+1=2。
- 增广 2：路径 \(s \to v1 \to t\)，流量 1，费用 2+3=5。
- 增广 3：路径 \(s \to v2 \to v1 \to t\)（通过反向边调整），流量 1，费用 1-1+2+3=5？等等，实际上需要更仔细的势能和最短路径计算，但最终会得到最大流 3，总费用最小为 8（具体数值需完整执行算法）。
通过这个示例，你可以看到 Capacity Scaling 首先尝试用 Δ=2 推送大流量，失败后降为 Δ=1 进行精细调整。
8. 总结
Capacity Scaling 算法的优势：
- 相比朴素 SSP，减少了最短路径计算的次数，尤其适用于容量值范围大、最大流值较大的情况。
- 保留了 SSP 的简单性和正确性。
适用场景：
- 最小费用最大流问题，边容量为整数。
- 适合容量范围大、但图规模中等的场景。
核心要点：
- 从大到小枚举容量阈值 Δ。
- 在每个 Δ 阶段，仅在容量足够的边上寻找最短增广路径。
- 结合势能函数，使用 Dijkstra 保证效率。
这样，我们就完成了最小费用最大流问题的 Capacity Scaling 算法的详细讲解。