最小成本流问题（Minimum Cost Flow, MCF）
字数 3623 2025-12-19 08:50:45

最小成本流问题（Minimum Cost Flow, MCF）

最小成本流问题（Minimum Cost Flow, MCF）是图论和网络流中的一个经典问题。它是在一个带有容量和成本的流网络中，寻找从源点到汇点满足特定流量需求的最小总成本的流。简单来说，我们不仅关心能流过多少流量（最大流问题），还关心以最低成本实现指定流量的输送。

问题描述

给定一个有向图 \(G = (V, E)\)，其中：

  • 每条边 \(e = (u, v) \in E\) 具有容量 \(c(e) \ge 0\) 和单位成本 \(p(e) \in \mathbb{R}\)。
  • 存在一个源点 \(s \in V\) 和一个汇点 \(t \in V\)。
  • 需要从 \(s\) 向 \(t\) 输送目标流量 \(F \ge 0\)。

目标：在满足以下约束的前提下，找到总成本最小的流方案：

  1. 容量约束：每条边 \(e\) 上的流量 \(f(e)\) 满足 \(0 \le f(e) \le c(e)\)。
  2. 流量守恒：对每个非源非汇的顶点 \(v \in V \setminus \{s, t\}\)，流出流量等于流入流量。
  3. 目标流量：从 \(s\) 流出的总流量（即流入 \(t\) 的总流量）恰好为 \(F\)。

总成本定义为：

\[\text{Cost}(f) = \sum_{e \in E} p(e) \cdot f(e) \]

解题思路

我们可以从简单的想法入手，逐步优化得到高效算法：

  1. 基本观察

    • 如果只需要满足流量 \(F\) 而不计成本，就是最大流问题。
    • 如果 \(F\) 超过了最大流，则无解。
    • 关键在于在满足流量和容量的同时，尽可能通过“便宜”的边输送流量。

  2. 关键思想：借助“残量网络”和“最短增广路”

    • 我们从零流（所有边流量为0）开始。
    • 在残量网络中寻找从 \(s\) 到 \(t\) 的最短（即单位成本最小）路径，并尽可能增加流量。
    • 但这里“最短”是指路径上边的单位成本之和最小吗？注意：正向边的成本为 \(p(e)\)，反向边的成本为 \(-p(e)\)（因为回流能减少成本）。
    • 然而，如果存在负成本边，或者负环路，则直接使用最短路径算法（如Dijkstra）可能失效。我们需要一种能处理负成本但无负环的算法，或者用“势函数”调整成本使所有边成本非负，从而能用Dijkstra加速。

  3. 主要算法：连续最短路算法（Successive Shortest Path Algorithm）

    • 这是求解MCF最常用的算法之一。其核心是每次在残量网络中找一条从 \(s\) 到 \(t\) 的最小单位成本路径，并沿其增加尽可能多的流量，直到达到目标流量 \(F\) 或确定无法达到。
    • 为了高效处理负成本边，引入“势（Potential）”和“约化成本（Reduced Cost）”的概念。

逐步详解

第1步：建立残量网络

对于当前流 \(f\)，定义残量网络 \(G_f = (V, E_f)\)，其中每条边 \(e = (u, v)\)：

  • 如果 \(f(e) < c(e)\)，则有一条正向边 \((u, v)\) 在 \(E_f\) 中，其残量容量为 \(c(e) - f(e)\)，单位成本为 \(p(e)\)。
  • 如果 \(f(e) > 0\)，则有一条反向边 \((v, u)\) 在 \(E_f\) 中，其残量容量为 \(f(e)\)，单位成本为 \(-p(e)\)（因为回流可抵消之前花费）。

第2步：引入势函数与约化成本

定义势函数 \(\phi: V \to \mathbb{R}\)。对残量网络中的每条边 \((u, v)\)，定义其约化成本：

\[p_\phi(u, v) = p(u, v) + \phi(u) - \phi(v) \]

关键性质：如果我们改变势函数，残量网络中任意路径的成本（按约化成本计算）与原成本只相差起点和终点的势值差。因此，在残量网络中寻找 \(s \to t\) 的最短路径，可以用约化成本代替原成本，只要保持所有约化成本非负，就能用Dijkstra算法快速求解。

第3步：初始化

  • 初始流 \(f\) 为零。
  • 初始势 \(\phi(v) = 0\) 对所有 \(v \in V\)。
  • 此时约化成本等于原成本，但原成本可能有负值，所以第一次找最短路需要用能处理负边的算法（如Bellman-Ford）计算从 \(s\) 到所有点的最短距离，并用这个距离更新势 \(\phi\)，使得之后约化成本非负。

第4步：主循环

当当前流量 \(\text{flow} < F\) 时：

  1. 在残量网络 \(G_f\) 中，以约化成本 \(p_\phi\) 为边权，用Dijkstra算法求从 \(s\) 到所有点的最短路径距离 \(d(v)\)（按约化成本）。
  2. 如果 \(t\) 不可达，说明无法输送更多流量，算法终止（无解）。
  3. 用 \(d(v)\) 更新势：\(\phi(v) := \phi(v) + d(v)\)。
  4. 沿着 \(s \to t\) 的最短路径（在原残量网络中，按 \(p_\phi\) 计算的最短路径），尽可能增加流量，增加量为该路径上残量容量的最小值，但不超过还需输送的流量 \(F - \text{flow}\)。
  5. 更新流量 \(\text{flow}\) 和残量网络。
  6. 重复。

第5步：正确性说明

  • 每次迭代沿最小约化成本路径增广，实际上是在当前残量网络中增广单位成本最小的路径（在势调整下等价于原成本最小）。
  • 由于每次增广后，新残量网络中所有边的约化成本仍保持非负（这是由势更新保证的），因此可以一直用Dijkstra高效找最短路。
  • 算法结束时，要么达到目标流量 \(F\)，要么提前无法再增广（即最大流量小于 \(F\)）。

时间复杂度

  • 初始Bellman-Ford：\(O(VE)\)。
  • 每次Dijkstra：\(O(E \log V)\) 或 \(O(V^2)\)（取决于实现）。
  • 最多增广 \(F\) 次（每次至少增加1单位流量）。但若容量和成本为整数，复杂度可表达为 \(O(F \cdot E \log V)\)。
  • 实践中，可用容量缩放（Capacity Scaling）或成本缩放（Cost Scaling）进一步优化，但此处不展开。

实例演示

考虑简单网络：

  • 顶点：\(s, a, t\)。
  • 边：
    \((s, a)\)：容量 3，成本 2。
    \((a, t)\)：容量 2，成本 5。
    \((s, t)\)：容量 2，成本 8。
  • 目标流量 \(F = 3\)。

步骤：

  1. 初始流为0，势全0。用Bellman-Ford（其实无负边）得 \(d(s)=0, d(a)=2, d(t)=8\)。更新势：\(\phi(s)=0, \phi(a)=2, \phi(t)=8\)。
  2. 约化成本：
    \(p_\phi(s,a)=2+0-2=0\)
    \(p_\phi(a,t)=5+2-8=-1\)（但注意反向边会不同，这里先看正向）
    实际上第一次Dijkstra在残量网络中边权为非负，我们直接求最短路：\(s \to a \to t\) 成本为 2+5=7，\(s \to t\) 成本为8。最短路径为 \(s \to a \to t\)，残量容量 min(3,2)=2，沿此路增广2单位流量。更新流：\(f(s,a)=2, f(a,t)=2\)，当前流量=2。
  3. 更新势：用Dijkstra在新残量网络中求最短路（从s出发）。此时 \((s,a)\) 残量1，成本2；\((a,t)\) 已满，无正向边，但有反向边 \((t,a)\) 成本-5；\((s,t)\) 残量2成本8。最短路径：\(s \to t\) 成本8。沿此路增广1单位（还需流量1），更新 \(f(s,t)=1\)，流量达到3，停止。
  4. 总成本 = \(2 \times 2 + 2 \times 5 + 1 \times 8 = 4+10+8=22\)。

小结

最小成本流问题在物流、通信、资源分配等领域应用广泛。连续最短路算法（Successive Shortest Path with Potentials）是其核心解法，它通过势函数调整边权，使得能用Dijkstra快速迭代，最终找到输送指定流量下的最小总成本流。

最小成本流问题（Minimum Cost Flow, MCF） 最小成本流问题（Minimum Cost Flow, MCF）是图论和网络流中的一个经典问题。它是在一个带有容量和成本的流网络中，寻找从源点到汇点满足特定流量需求的最小总成本的流。简单来说，我们不仅关心能流过多少流量（最大流问题），还关心以最低成本实现指定流量的输送。 问题描述 给定一个 有向图 \( G = (V, E) \)，其中： 每条边 \( e = (u, v) \in E \) 具有 容量 \( c(e) \ge 0 \) 和 单位成本 \( p(e) \in \mathbb{R} \)。 存在一个 源点 \( s \in V \) 和一个 汇点 \( t \in V \)。 需要从 \( s \) 向 \( t \) 输送 目标流量 \( F \ge 0 \)。 目标 ：在满足以下约束的前提下，找到总成本最小的流方案： 容量约束 ：每条边 \( e \) 上的流量 \( f(e) \) 满足 \( 0 \le f(e) \le c(e) \)。 流量守恒 ：对每个非源非汇的顶点 \( v \in V \setminus \{s, t\} \)，流出流量等于流入流量。 目标流量 ：从 \( s \) 流出的总流量（即流入 \( t \) 的总流量）恰好为 \( F \)。 总成本 定义为： \[ \text{Cost}(f) = \sum_ {e \in E} p(e) \cdot f(e) \] 解题思路 我们可以从简单的想法入手，逐步优化得到高效算法： 基本观察 如果只需要满足流量 \( F \) 而不计成本，就是最大流问题。 如果 \( F \) 超过了最大流，则无解。 关键在于在满足流量和容量的同时，尽可能通过“便宜”的边输送流量。 关键思想：借助“残量网络”和“最短增广路” 我们从零流（所有边流量为0）开始。 在 残量网络 中寻找从 \( s \) 到 \( t \) 的最短（即单位成本最小）路径，并尽可能增加流量。 但这里“最短”是指路径上边的单位成本之和最小吗？注意：正向边的成本为 \( p(e) \)，反向边的成本为 \( -p(e) \)（因为回流能减少成本）。 然而，如果存在负成本边，或者负环路，则直接使用最短路径算法（如Dijkstra）可能失效。我们需要一种能处理负成本但无负环的算法，或者用“势函数”调整成本使所有边成本非负，从而能用Dijkstra加速。 主要算法：连续最短路算法（Successive Shortest Path Algorithm） 这是求解MCF最常用的算法之一。其核心是每次在残量网络中找一条从 \( s \) 到 \( t \) 的 最小单位成本路径 ，并沿其增加尽可能多的流量，直到达到目标流量 \( F \) 或确定无法达到。 为了高效处理负成本边，引入“势（Potential）”和“约化成本（Reduced Cost）”的概念。 逐步详解 第1步：建立残量网络 对于当前流 \( f \)，定义残量网络 \( G_ f = (V, E_ f) \)，其中每条边 \( e = (u, v) \)： 如果 \( f(e) < c(e) \)，则有一条正向边 \( (u, v) \) 在 \( E_ f \) 中，其残量容量为 \( c(e) - f(e) \)，单位成本为 \( p(e) \)。 如果 \( f(e) > 0 \)，则有一条反向边 \( (v, u) \) 在 \( E_ f \) 中，其残量容量为 \( f(e) \)，单位成本为 \( -p(e) \)（因为回流可抵消之前花费）。 第2步：引入势函数与约化成本 定义势函数 \( \phi: V \to \mathbb{R} \)。对残量网络中的每条边 \( (u, v) \)，定义其 约化成本 ： \[ p_ \phi(u, v) = p(u, v) + \phi(u) - \phi(v) \] 关键性质：如果我们改变势函数，残量网络中任意路径的成本（按约化成本计算）与原成本只相差起点和终点的势值差。因此，在残量网络中寻找 \( s \to t \) 的最短路径，可以用约化成本代替原成本，只要 保持所有约化成本非负 ，就能用Dijkstra算法快速求解。 第3步：初始化 初始流 \( f \) 为零。 初始势 \( \phi(v) = 0 \) 对所有 \( v \in V \)。 此时约化成本等于原成本，但原成本可能有负值，所以第一次找最短路需要用能处理负边的算法（如Bellman-Ford）计算从 \( s \) 到所有点的最短距离，并用这个距离更新势 \( \phi \)，使得之后约化成本非负。 第4步：主循环 当当前流量 \( \text{flow} < F \) 时： 在残量网络 \( G_ f \) 中，以约化成本 \( p_ \phi \) 为边权，用Dijkstra算法求从 \( s \) 到所有点的最短路径距离 \( d(v) \)（按约化成本）。 如果 \( t \) 不可达，说明无法输送更多流量，算法终止（无解）。 用 \( d(v) \) 更新势：\( \phi(v) := \phi(v) + d(v) \)。 沿着 \( s \to t \) 的最短路径（在原残量网络中，按 \( p_ \phi \) 计算的最短路径），尽可能增加流量，增加量为该路径上残量容量的最小值，但不超过还需输送的流量 \( F - \text{flow} \)。 更新流量 \( \text{flow} \) 和残量网络。 重复。 第5步：正确性说明 每次迭代沿最小约化成本路径增广，实际上是在当前残量网络中增广单位成本最小的路径（在势调整下等价于原成本最小）。 由于每次增广后，新残量网络中所有边的约化成本仍保持非负（这是由势更新保证的），因此可以一直用Dijkstra高效找最短路。 算法结束时，要么达到目标流量 \( F \)，要么提前无法再增广（即最大流量小于 \( F \)）。 时间复杂度 初始Bellman-Ford：\( O(VE) \)。 每次Dijkstra：\( O(E \log V) \) 或 \( O(V^2) \)（取决于实现）。 最多增广 \( F \) 次（每次至少增加1单位流量）。但若容量和成本为整数，复杂度可表达为 \( O(F \cdot E \log V) \)。 实践中，可用容量缩放（Capacity Scaling）或成本缩放（Cost Scaling）进一步优化，但此处不展开。 实例演示 考虑简单网络： 顶点：\( s, a, t \)。 边： \( (s, a) \)：容量 3，成本 2。 \( (a, t) \)：容量 2，成本 5。 \( (s, t) \)：容量 2，成本 8。 目标流量 \( F = 3 \)。 步骤： 初始流为0，势全0。用Bellman-Ford（其实无负边）得 \( d(s)=0, d(a)=2, d(t)=8 \)。更新势：\( \phi(s)=0, \phi(a)=2, \phi(t)=8 \)。 约化成本： \( p_ \phi(s,a)=2+0-2=0 \) \( p_ \phi(a,t)=5+2-8=-1 \)（但注意反向边会不同，这里先看正向） 实际上第一次Dijkstra在残量网络中边权为非负，我们直接求最短路：\( s \to a \to t \) 成本为 2+5=7，\( s \to t \) 成本为8。最短路径为 \( s \to a \to t \)，残量容量 min(3,2)=2，沿此路增广2单位流量。更新流：\( f(s,a)=2, f(a,t)=2 \)，当前流量=2。 更新势：用Dijkstra在新残量网络中求最短路（从s出发）。此时 \( (s,a) \) 残量1，成本2；\( (a,t) \) 已满，无正向边，但有反向边 \( (t,a) \) 成本-5；\( (s,t) \) 残量2成本8。最短路径：\( s \to t \) 成本8。沿此路增广1单位（还需流量1），更新 \( f(s,t)=1 \)，流量达到3，停止。 总成本 = \( 2 \times 2 + 2 \times 5 + 1 \times 8 = 4+10+8=22 \)。 小结 最小成本流问题在物流、通信、资源分配等领域应用广泛。连续最短路算法（Successive Shortest Path with Potentials）是其核心解法，它通过势函数调整边权，使得能用Dijkstra快速迭代，最终找到输送指定流量下的最小总成本流。