最小成本流问题（Minimum Cost Flow, MCF）的Capacity Scaling算法
字数 3666 2025-12-24 15:12:52

最小成本流问题（Minimum Cost Flow, MCF）的Capacity Scaling算法

题目描述
我们有一个有向图 \(G=(V, E)\)，每条边 \(e \in E\) 有一个容量 \(u(e) \geq 0\) 和一个单位流量成本 \(c(e)\)（可为负）。同时，每个顶点 \(v \in V\) 有一个供需量 \(b(v)\)：若 \(b(v) > 0\)，表示它是供应点（源），需要净流出 \(b(v)\) 单位的流量；若 \(b(v) < 0\)，表示它是需求点（汇），需要净流入 \(|b(v)|\) 单位的流量；若 \(b(v) = 0\)，则是转运点。最小成本流（MCF）问题的目标是找到一组流 \(f(e)\) 满足：

  1. 容量限制：\(0 \leq f(e) \leq u(e)\)；
  2. 流量守恒：对每个顶点 \(v\)，流出量减去流入量等于 \(b(v)\)；
  3. 总成本 \(\sum_{e \in E} c(e) f(e)\) 最小。

Capacity Scaling 算法是一种求解 MCF 问题的强多项式算法，它通过逐步缩小容量缩放因子 \(\Delta\)，在每次迭代中只考虑容量至少为 \(\Delta\) 的边，寻找一组能发送一定流量的“增广流”以改进当前解，最终得到最优流。

解题过程

1. 问题预处理与基本概念
首先，我们需要确保问题可行。可行条件为：所有顶点的供需之和为零，即 \(\sum_{v \in V} b(v) = 0\)。如果存在负成本边，算法依然能处理，但为了方便理解，我们先假设所有成本非负（实际算法可处理负成本，可通过引入势能或预处理消除负边）。

算法维护一个可行流 \(f\) 和一组顶点势能 \(\pi\)（用于处理负成本边，本讲解侧重非负成本情形，可暂忽略势能）。核心思想是：从一个大尺度 \(\Delta\) 开始，只考虑“大容量”边（剩余容量 \(\geq \Delta\)），尝试沿这些边发送尽量多的流量以满足供需，然后逐步将 \(\Delta\) 减半，重复直到 \(\Delta < 1\)，此时流即为最优。

2. 算法框架

  • 初始化：设 \(U = \max\{u(e) : e \in E\}\)，取 \(\Delta = 2^{\lfloor \log_2 U \rfloor}\)（即不超过 \(U\) 的最大2的幂）。初始流 \(f(e)=0\)，顶点势能 \(\pi(v)=0\)。
  • 主循环：当 \(\Delta \geq 1\) 时重复以下步骤：
    a. 容量缩放网络构建：在当前流 \(f\) 下，定义剩余网络 \(G_f\)，但只保留剩余容量 \(r(e) = u(e) - f(e) \geq \Delta\) 的边（前向边）和流量 \(f(e) \geq \Delta\) 的边（可推送回流，即反向边）。注意：反向边的成本是原边成本的相反数。
    b. \(\Delta\)-供需平衡：计算每个顶点 \(v\) 的“未满足供需” \(b'(v) = b(v) - (\text{流出量} - \text{流入量})\)。在剩余网络中，尝试通过发送流量来减少 \(|b'(v)|\)，但每次发送的流量至少为 \(\Delta\)。
    c. 寻找增广流：在容量缩放网络中，重复以下操作直到所有顶点满足 \(b'(v)=0\) 或无法继续：
    • 若存在供应点 \(s\)（\(b'(s) > 0\)）和需求点 \(t\)（\(b'(t) < 0\)），在容量缩放网络中找一条从 \(s\) 到 \(t\) 的最短路径（按边成本）。
    • 沿该路径推送尽可能多的流量，但不超过 \(\min\{b'(s), -b'(t), \text{路径最小剩余容量}\}\)，且推送量至少为 \(\Delta\)（实际取 \(\Delta\) 的整数倍）。
    • 更新流 \(f\) 和顶点未满足供需 \(b'\)。
      d. 将 \(\Delta\) 减半：\(\Delta \leftarrow \Delta / 2\)。
  • 结束：当 \(\Delta < 1\) 时，当前流 \(f\) 即为最小成本流。

3. 为何要逐步缩放？
如果直接在所有边上找最短路径增广（如Successive Shortest Path算法），每次增广量可能很小，导致增广次数多，效率低。Capacity Scaling 先在大容量边上发送“大流量”，快速满足大部分供需，然后逐步细化到小容量边。这相当于一种“二分搜索”思想，将问题分解为 \(O(\log U)\) 个阶段，每阶段内处理的网络边数较少（只考虑剩余容量 \(\geq \Delta\) 的边），从而提升效率。

4. 详细步骤示例
假设有一个简单图：顶点 \(V=\{1,2,3\}\)，边 \(E=\{(1,2), (2,3), (1,3)\}\)，容量均为 \(u=4\)，成本 \(c(1,2)=1, c(2,3)=2, c(1,3)=5\)。供需 \(b(1)=3, b(2)=0, b(3)=-3\)（顶点1供应3单位，顶点3需求3单位）。

  • 初始化：\(U=4, \Delta=4\)。初始流 \(f=0\)，未满足供需 \(b' = b = [3,0,-3]\)。
  • 阶段 \(\Delta=4\)：
    • 容量缩放网络：所有边剩余容量 \(r=4 \geq 4\)，故包含全部前向边（无反向边，因 \(f=0\)）。
    • 找增广流：供应点1到需求点3的最短路径是 \(1 \rightarrow 2 \rightarrow 3\)，成本 \(1+2=3\)。路径最小容量为4，但可发送流量受供需限制：\(\min(b'(1)=3, -b'(3)=3, 4)=3\)。由于 \(3 < \Delta=4\)，本阶段不发送任何流量（因为要求至少发送 \(\Delta\) 流量）。注意：实际操作中，若可发送量 \(< \Delta\)，则跳过，等待 \(\Delta\) 变小后再处理。
    • 更新：无流量变化，\(b'\) 不变。
  • 将 \(\Delta\) 减半：\(\Delta=2\)。
  • 阶段 \(\Delta=2\)：
    • 容量缩放网络：剩余容量仍均为4 \(\geq 2\)，网络不变。
    • 增广流：相同最短路径 \(1 \rightarrow 2 \rightarrow 3\)，可发送流量为3，现在3 \(\geq \Delta=2\)，因此发送3单位流量。
    • 更新：沿路径发送3单位，\(f(1,2)=3, f(2,3)=3\)，成本 \(3 \times 3 = 9\)。更新 \(b'(1)=0, b'(3)=0\)，供需已满足。
  • 后续 \(\Delta=1,0.5,...\) 阶段：由于 \(b'\) 已全零，算法终止。

得到最终流：\(f(1,2)=3, f(2,3)=3, f(1,3)=0\)，总成本9。可验证这是最小成本解（若走 \(1 \rightarrow 3\) 直接边，成本 \(5 \times 3=15 > 9\)）。

5. 算法正确性直观解释
每阶段结束时，当前流是关于当前 \(\Delta\) 的“\(\Delta\)-最优”流，即不存在成本为负的、剩余容量至少为 \(\Delta\) 的增广圈。当 \(\Delta\) 足够小时（如 \(\Delta < 1\)，容量为整数时 \(\Delta < 1\) 意味着 \(\Delta=0\)），流就是最优的。这是因为最小成本流的充要条件是不存在负成本增广圈（负圈最优性定理），而 \(\Delta\) 逐步减小确保了最终满足该条件。

6. 时间复杂度
Capacity Scaling 算法的时间复杂度为 \(O((m \log U)(m + n \log n))\)，其中 \(m=|E|, n=|V|\)。因子 \(\log U\) 是缩放阶段数，每阶段内需多次找最短路径（可用 Dijkstra 算法，若无非负成本则用 Bellman-Ford 预处理势能），每次增广至少减少一个顶点的未满足供需，故每阶段增广次数为 \(O(n)\)。该复杂度是强多项式的，优于简单的连续最短路径算法。

7. 扩展：处理负成本边
若图中存在负成本边，可在每阶段开始时，先用 Bellman-Ford 算法更新顶点势能 \(\pi\)，使得缩放网络中的所有边成本经变换 \(c'(e)=c(e)+\pi(u)-\pi(v)\) 后非负，从而可使用高效的最短路径算法。势能更新保证了最优性条件不变。

总结
Capacity Scaling 算法通过“由粗到细”的容量缩放，逐步逼近最小成本流。它在每阶段聚焦于大容量边，批量发送流量，减少了增广次数，是求解最小成本流问题的一种高效且易于实现的强多项式算法。

最小成本流问题（Minimum Cost Flow, MCF）的Capacity Scaling算法 题目描述 我们有一个有向图 \(G=(V, E)\)，每条边 \(e \in E\) 有一个容量 \(u(e) \geq 0\) 和一个单位流量成本 \(c(e)\)（可为负）。同时，每个顶点 \(v \in V\) 有一个供需量 \(b(v)\)：若 \(b(v) > 0\)，表示它是供应点（源），需要净流出 \(b(v)\) 单位的流量；若 \(b(v) < 0\)，表示它是需求点（汇），需要净流入 \(|b(v)|\) 单位的流量；若 \(b(v) = 0\)，则是转运点。最小成本流（MCF）问题的目标是找到一组流 \(f(e)\) 满足： 容量限制：\(0 \leq f(e) \leq u(e)\)； 流量守恒：对每个顶点 \(v\)，流出量减去流入量等于 \(b(v)\)； 总成本 \(\sum_ {e \in E} c(e) f(e)\) 最小。 Capacity Scaling 算法是一种求解 MCF 问题的强多项式算法，它通过逐步缩小容量缩放因子 \(\Delta\)，在每次迭代中只考虑容量至少为 \(\Delta\) 的边，寻找一组能发送一定流量的“增广流”以改进当前解，最终得到最优流。 解题过程 1. 问题预处理与基本概念 首先，我们需要确保问题可行。可行条件为：所有顶点的供需之和为零，即 \(\sum_ {v \in V} b(v) = 0\)。如果存在负成本边，算法依然能处理，但为了方便理解，我们先假设所有成本非负（实际算法可处理负成本，可通过引入势能或预处理消除负边）。 算法维护一个可行流 \(f\) 和一组顶点势能 \(\pi\)（用于处理负成本边，本讲解侧重非负成本情形，可暂忽略势能）。核心思想是：从一个大尺度 \(\Delta\) 开始，只考虑“大容量”边（剩余容量 \(\geq \Delta\)），尝试沿这些边发送尽量多的流量以满足供需，然后逐步将 \(\Delta\) 减半，重复直到 \(\Delta < 1\)，此时流即为最优。 2. 算法框架 初始化：设 \(U = \max\{u(e) : e \in E\}\)，取 \(\Delta = 2^{\lfloor \log_ 2 U \rfloor}\)（即不超过 \(U\) 的最大2的幂）。初始流 \(f(e)=0\)，顶点势能 \(\pi(v)=0\)。 主循环：当 \(\Delta \geq 1\) 时重复以下步骤： a. 容量缩放网络构建 ：在当前流 \(f\) 下，定义剩余网络 \(G_ f\)，但只保留剩余容量 \(r(e) = u(e) - f(e) \geq \Delta\) 的边（前向边）和流量 \(f(e) \geq \Delta\) 的边（可推送回流，即反向边）。注意：反向边的成本是原边成本的相反数。 b. \(\Delta\)-供需平衡 ：计算每个顶点 \(v\) 的“未满足供需” \(b'(v) = b(v) - (\text{流出量} - \text{流入量})\)。在剩余网络中，尝试通过发送流量来减少 \(|b'(v)|\)，但每次发送的流量至少为 \(\Delta\)。 c. 寻找增广流 ：在容量缩放网络中，重复以下操作直到所有顶点满足 \(b'(v)=0\) 或无法继续： 若存在供应点 \(s\)（\(b'(s) > 0\)）和需求点 \(t\)（\(b'(t) < 0\)），在容量缩放网络中找一条从 \(s\) 到 \(t\) 的最短路径（按边成本）。 沿该路径推送尽可能多的流量，但不超过 \(\min\{b'(s), -b'(t), \text{路径最小剩余容量}\}\)，且推送量至少为 \(\Delta\)（实际取 \(\Delta\) 的整数倍）。 更新流 \(f\) 和顶点未满足供需 \(b'\)。 d. 将 \(\Delta\) 减半：\(\Delta \leftarrow \Delta / 2\)。 结束：当 \(\Delta < 1\) 时，当前流 \(f\) 即为最小成本流。 3. 为何要逐步缩放？ 如果直接在所有边上找最短路径增广（如Successive Shortest Path算法），每次增广量可能很小，导致增广次数多，效率低。Capacity Scaling 先在大容量边上发送“大流量”，快速满足大部分供需，然后逐步细化到小容量边。这相当于一种“二分搜索”思想，将问题分解为 \(O(\log U)\) 个阶段，每阶段内处理的网络边数较少（只考虑剩余容量 \(\geq \Delta\) 的边），从而提升效率。 4. 详细步骤示例 假设有一个简单图：顶点 \(V=\{1,2,3\}\)，边 \(E=\{(1,2), (2,3), (1,3)\}\)，容量均为 \(u=4\)，成本 \(c(1,2)=1, c(2,3)=2, c(1,3)=5\)。供需 \(b(1)=3, b(2)=0, b(3)=-3\)（顶点1供应3单位，顶点3需求3单位）。 初始化：\(U=4, \Delta=4\)。初始流 \(f=0\)，未满足供需 \(b' = b = [ 3,0,-3 ]\)。 阶段 \(\Delta=4\)： 容量缩放网络：所有边剩余容量 \(r=4 \geq 4\)，故包含全部前向边（无反向边，因 \(f=0\)）。 找增广流：供应点1到需求点3的最短路径是 \(1 \rightarrow 2 \rightarrow 3\)，成本 \(1+2=3\)。路径最小容量为4，但可发送流量受供需限制：\(\min(b'(1)=3, -b'(3)=3, 4)=3\)。由于 \(3 < \Delta=4\)，本阶段不发送任何流量（因为要求至少发送 \(\Delta\) 流量）。注意：实际操作中，若可发送量 \( < \Delta\)，则跳过，等待 \(\Delta\) 变小后再处理。 更新：无流量变化，\(b'\) 不变。 将 \(\Delta\) 减半：\(\Delta=2\)。 阶段 \(\Delta=2\)： 容量缩放网络：剩余容量仍均为4 \(\geq 2\)，网络不变。 增广流：相同最短路径 \(1 \rightarrow 2 \rightarrow 3\)，可发送流量为3，现在3 \(\geq \Delta=2\)，因此发送3单位流量。 更新：沿路径发送3单位，\(f(1,2)=3, f(2,3)=3\)，成本 \(3 \times 3 = 9\)。更新 \(b'(1)=0, b'(3)=0\)，供需已满足。 后续 \(\Delta=1,0.5,...\) 阶段：由于 \(b'\) 已全零，算法终止。 得到最终流：\(f(1,2)=3, f(2,3)=3, f(1,3)=0\)，总成本9。可验证这是最小成本解（若走 \(1 \rightarrow 3\) 直接边，成本 \(5 \times 3=15 > 9\)）。 5. 算法正确性直观解释 每阶段结束时，当前流是关于当前 \(\Delta\) 的“\(\Delta\)-最优”流，即不存在成本为负的、剩余容量至少为 \(\Delta\) 的增广圈。当 \(\Delta\) 足够小时（如 \(\Delta < 1\)，容量为整数时 \(\Delta < 1\) 意味着 \(\Delta=0\)），流就是最优的。这是因为最小成本流的充要条件是不存在负成本增广圈（负圈最优性定理），而 \(\Delta\) 逐步减小确保了最终满足该条件。 6. 时间复杂度 Capacity Scaling 算法的时间复杂度为 \(O((m \log U)(m + n \log n))\)，其中 \(m=|E|, n=|V|\)。因子 \(\log U\) 是缩放阶段数，每阶段内需多次找最短路径（可用 Dijkstra 算法，若无非负成本则用 Bellman-Ford 预处理势能），每次增广至少减少一个顶点的未满足供需，故每阶段增广次数为 \(O(n)\)。该复杂度是强多项式的，优于简单的连续最短路径算法。 7. 扩展：处理负成本边 若图中存在负成本边，可在每阶段开始时，先用 Bellman-Ford 算法更新顶点势能 \(\pi\)，使得缩放网络中的所有边成本经变换 \(c'(e)=c(e)+\pi(u)-\pi(v)\) 后非负，从而可使用高效的最短路径算法。势能更新保证了最优性条件不变。 总结 Capacity Scaling 算法通过“由粗到细”的容量缩放，逐步逼近最小成本流。它在每阶段聚焦于大容量边，批量发送流量，减少了增广次数，是求解最小成本流问题的一种高效且易于实现的强多项式算法。