最小成本流问题（Minimum Cost Flow, MCF）
字数 3454 2025-12-16 15:10:33

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

题目描述
给定一个有向图 \(G = (V, E)\)，其中每条边 \(e \in E\) 有两个属性：

  • 容量 \(c(e) \geq 0\)，表示该边允许通过的最大流量。
  • 单位流成本 \(w(e)\)，表示每单位流量通过该边产生的费用。

同时，每个顶点 \(v \in V\) 有一个净需求量（supply/demand） \(b(v)\)，满足：

  • 若 \(b(v) > 0\)，则 \(v\) 是供应点（supply node），表示它需要向外“净流出” \(b(v)\) 单位的流量。
  • 若 \(b(v) < 0\)，则 \(v\) 是需求点（demand node），表示它需要“净流入” \(|b(v)|\) 单位的流量。
  • 且所有顶点的净需求量之和为零，即 \(\sum_{v \in V} b(v) = 0\)。

目标是：找到一组流量 \(f(e)\) 分配在所有边上，满足以下条件：

  1. 容量限制：对每条边 \(e\)，有 \(0 \leq f(e) \leq c(e)\)。
  2. 流量守恒：对每个顶点 \(v\)，流入的总流量减去流出的总流量等于 \(b(v)\)。
  3. 总成本最小化：总成本 \(\sum_{e \in E} w(e) \cdot f(e)\) 尽可能小。

这个问题是网络流中的经典问题，广泛应用于物流、调度、资源分配等场景。

解题过程循序渐进讲解

第一步：理解问题与建模
问题的核心是在满足容量和流量守恒约束下，最小化总成本。我们可以将图 \(G\) 中的每条边看作一个“运输通道”：容量限制了最大运输量，单位成本决定了运输单价。供应点（如仓库）提供货物，需求点（如商店）消耗货物，我们需要规划一个运输方案，使得总运输费用最低。

形式化表示：

  • 决策变量：对每条边 \(e = (u, v)\)，流量 \(f_{uv}\)。
  • 目标：最小化 \(\sum_{(u,v) \in E} w_{uv} f_{uv}\)。
  • 约束：
    (1) 容量约束：\(0 \leq f_{uv} \leq c_{uv}\)。
    (2) 守恒约束：对所有 \(v \in V\)，有

\[ \sum_{(u,v) \in E} f_{uv} - \sum_{(v,u) \in E} f_{vu} = b(v). \]

这里第一个和是流入 \(v\) 的流量，第二个和是流出 \(v\) 的流量。

第二步：转换为最小费用最大流（Min-Cost Max-Flow）形式
许多算法假设只有一个源点（供应点之和）和一个汇点（需求点之和）。为此，我们可以将原问题转化为一个等效的单源单汇最小费用最大流问题：

  1. 添加一个超级源点 \(s\) 和一个超级汇点 \(t\)。
  2. 对每个供应点 \(v\)（即 \(b(v) > 0\)），从 \(s\) 到 \(v\) 加一条边，容量为 \(b(v)\)，单位成本为 0。
  3. 对每个需求点 \(v\)（即 \(b(v) < 0\)），从 \(v\) 到 \(t\) 加一条边，容量为 \(-b(v)\)，单位成本为 0。
  4. 此时，原图中的顶点 \(v\) 的净需求量变为 0（即成为中转点），目标变为从 \(s\) 到 \(t\) 输送 \(D = \sum_{b(v)>0} b(v)\) 的总流量，并最小化成本。

这样，问题转化为：在扩展后的网络中，寻找流量恰好为 \(D\) 的最小费用流（如果可行）。

第三步：算法思想——Successive Shortest Path（连续最短路）算法
这是解决最小成本流问题最直观的算法之一。它的核心思想是：每次沿着当前残量网络中从源点到汇点的最短（单位成本）可增广路径推送尽可能多的流量，直到达到所需总流量 \(D\)。

为什么用“最短路径”？
在残量网络中，每条边的剩余容量对应一个“可使用”的运输机会，而每条边的单位成本决定了增广该边带来的费用变化。从 \(s\) 到 \(t\) 的一条路径的总成本就是沿该路径输送一单位流量增加的总费用。为了最小化总成本，我们应该优先使用“当前单位成本增量最小”的路径，即最短路径。

第四步：算法详细步骤
设初始流量 \(f = 0\)，当前总流量 \(F = 0\)。我们需要在残量网络 \(G_f\) 中重复寻找最短路径并增广。

1. 构造残量网络：
残量网络 \(G_f\) 的构建与最大流问题类似，但每条边有“残量容量”和“残量成本”：

  • 对原边 \((u,v)\) 容量 \(c\)、成本 \(w\)：若当前流量 \(f_{uv} < c\)，则在 \(G_f\) 中加入一条有向边 \(u \to v\)，残量容量为 \(c - f_{uv}\)，残量成本为 \(w\)。
  • 同时，为了允许“退回”流量（即减少正向流量），对每条有流量的边 \((u,v)\)（即 \(f_{uv} > 0\)），在 \(G_f\) 中加入反向边 \(v \to u\)，残量容量为 \(f_{uv}\)，残量成本为 \(-w\)。这表示取消一单位正向流量可节省 \(w\) 的费用。

2. 在 \(G_f\) 中找从 \(s\) 到 \(t\) 的最短路径：
这里的“最短”指路径上边的残量成本之和最小。由于可能存在负成本边（来自反向边），不能直接用 Dijkstra 算法（除非所有边非负）。处理办法：

  • 如果原图中没有负环，且初始所有边成本非负，则通过引入“势函数（potential）”可以使所有残量成本非负，从而可用 Dijkstra 算法高效求最短路径。
  • 势函数 \(p(v)\) 的维护：开始时 \(p(v) = 0\)；每次用 Bellman-Ford 或 SPFA 计算一次从 \(s\) 出发的最短距离 \(dist(v)\)，然后更新 \(p(v) := p(v) + dist(v)\)。调整后的边成本 \(w_p'(u,v) = w(u,v) + p(u) - p(v)\) 可证明非负，之后便可用 Dijkstra 算法。这是算法中的关键优化技巧。

3. 增广：
找到最短路径后，设该路径的残量容量最小值为 \(\Delta\)（即瓶颈容量），实际可推送流量为 \(\min(\Delta, D - F)\)。沿路径更新残量网络中的容量（正向边减流量，反向边加流量），并更新当前总流量 \(F\) 和总成本。

4. 重复：
重复步骤 2–3，直到 \(F = D\)（即达到所需总流量）。如果中途无法再找到从 \(s\) 到 \(t\) 的路径，说明无可行流。

第五步：算法正确性直观理解
这个算法实际上是在模拟“连续贪心”策略：每次增加一单位流量时，都选择当前最便宜的路径。由于成本是线性的（单位成本固定），且没有负环（否则可无限降低成本，无有限最优解），这个贪心策略能保证最终得到最小成本流。数学上，这等价于在每一步保持“互补松弛条件”，最终到达最优解。

第六步：时间复杂度

  • 每次增广至少增加 1 单位流量，最多增广 \(D\) 次。
  • 每次找最短路径：若用 SPFA（容许负边），为 \(O(VE)\)；若用势函数+Dijkstra，为 \(O(E \log V)\)。
  • 总复杂度：若用势函数+Dijkstra，为 \(O(D \cdot E \log V)\)。当 \(D\) 很大时可能较慢，但实践中常通过容量缩放（Capacity Scaling）优化，每次沿最短路径推送尽可能大的流量，减少增广次数。

总结
最小成本流问题是一个典型的网络优化问题，Successive Shortest Path 算法通过连续寻找最小成本增广路径来逐步构建最优流。关键点包括：转化为单源单汇问题、维护残量网络、用势函数+Dijkstra 高效求最短路径。这个算法是许多实际运输与调度问题的核心解法。

最小成本流问题（Minimum Cost Flow, MCF） 题目描述 给定一个有向图 \( G = (V, E) \)，其中每条边 \( e \in E \) 有两个属性： 容量 \( c(e) \geq 0 \)，表示该边允许通过的最大流量。 单位流成本 \( w(e) \)，表示每单位流量通过该边产生的费用。 同时，每个顶点 \( v \in V \) 有一个净需求量（supply/demand） \( b(v) \)，满足： 若 \( b(v) > 0 \)，则 \( v \) 是供应点（supply node），表示它需要向外“净流出” \( b(v) \) 单位的流量。 若 \( b(v) < 0 \)，则 \( v \) 是需求点（demand node），表示它需要“净流入” \( |b(v)| \) 单位的流量。 且所有顶点的净需求量之和为零，即 \( \sum_ {v \in V} b(v) = 0 \)。 目标是：找到一组流量 \( f(e) \) 分配在所有边上，满足以下条件： 容量限制：对每条边 \( e \)，有 \( 0 \leq f(e) \leq c(e) \)。 流量守恒：对每个顶点 \( v \)，流入的总流量减去流出的总流量等于 \( b(v) \)。 总成本最小化：总成本 \( \sum_ {e \in E} w(e) \cdot f(e) \) 尽可能小。 这个问题是网络流中的经典问题，广泛应用于物流、调度、资源分配等场景。 解题过程循序渐进讲解 第一步：理解问题与建模 问题的核心是在满足容量和流量守恒约束下，最小化总成本。我们可以将图 \( G \) 中的每条边看作一个“运输通道”：容量限制了最大运输量，单位成本决定了运输单价。供应点（如仓库）提供货物，需求点（如商店）消耗货物，我们需要规划一个运输方案，使得总运输费用最低。 形式化表示 ： 决策变量：对每条边 \( e = (u, v) \)，流量 \( f_ {uv} \)。 目标：最小化 \( \sum_ {(u,v) \in E} w_ {uv} f_ {uv} \)。 约束： (1) 容量约束：\( 0 \leq f_ {uv} \leq c_ {uv} \)。 (2) 守恒约束：对所有 \( v \in V \)，有 \[ \sum_ {(u,v) \in E} f_ {uv} - \sum_ {(v,u) \in E} f_ {vu} = b(v). \] 这里第一个和是流入 \( v \) 的流量，第二个和是流出 \( v \) 的流量。 第二步：转换为最小费用最大流（Min-Cost Max-Flow）形式 许多算法假设只有一个源点（供应点之和）和一个汇点（需求点之和）。为此，我们可以将原问题转化为一个等效的单源单汇最小费用最大流问题： 添加一个超级源点 \( s \) 和一个超级汇点 \( t \)。 对每个供应点 \( v \)（即 \( b(v) > 0 \)），从 \( s \) 到 \( v \) 加一条边，容量为 \( b(v) \)，单位成本为 0。 对每个需求点 \( v \)（即 \( b(v) < 0 \)），从 \( v \) 到 \( t \) 加一条边，容量为 \( -b(v) \)，单位成本为 0。 此时，原图中的顶点 \( v \) 的净需求量变为 0（即成为中转点），目标变为从 \( s \) 到 \( t \) 输送 \( D = \sum_ {b(v)>0} b(v) \) 的总流量，并最小化成本。 这样，问题转化为：在扩展后的网络中，寻找流量恰好为 \( D \) 的最小费用流（如果可行）。 第三步：算法思想——Successive Shortest Path（连续最短路）算法 这是解决最小成本流问题最直观的算法之一。它的核心思想是： 每次沿着当前残量网络中从源点到汇点的最短（单位成本）可增广路径推送尽可能多的流量，直到达到所需总流量 \( D \)。 为什么用“最短路径”？ 在残量网络中，每条边的剩余容量对应一个“可使用”的运输机会，而每条边的单位成本决定了增广该边带来的费用变化。从 \( s \) 到 \( t \) 的一条路径的总成本就是沿该路径输送一单位流量增加的总费用。为了最小化总成本，我们应该优先使用“当前单位成本增量最小”的路径，即最短路径。 第四步：算法详细步骤 设初始流量 \( f = 0 \)，当前总流量 \( F = 0 \)。我们需要在残量网络 \( G_ f \) 中重复寻找最短路径并增广。 1. 构造残量网络 ： 残量网络 \( G_ f \) 的构建与最大流问题类似，但每条边有“残量容量”和“残量成本”： 对原边 \( (u,v) \) 容量 \( c \)、成本 \( w \)：若当前流量 \( f_ {uv} < c \)，则在 \( G_ f \) 中加入一条有向边 \( u \to v \)，残量容量为 \( c - f_ {uv} \)，残量成本为 \( w \)。 同时，为了允许“退回”流量（即减少正向流量），对每条有流量的边 \( (u,v) \)（即 \( f_ {uv} > 0 \)），在 \( G_ f \) 中加入反向边 \( v \to u \)，残量容量为 \( f_ {uv} \)，残量成本为 \( -w \)。这表示取消一单位正向流量可节省 \( w \) 的费用。 2. 在 \( G_ f \) 中找从 \( s \) 到 \( t \) 的最短路径 ： 这里的“最短”指路径上边的残量成本之和最小。由于可能存在负成本边（来自反向边），不能直接用 Dijkstra 算法（除非所有边非负）。处理办法： 如果原图中没有负环，且初始所有边成本非负，则通过引入“势函数（potential）”可以使所有残量成本非负，从而可用 Dijkstra 算法高效求最短路径。 势函数 \( p(v) \) 的维护：开始时 \( p(v) = 0 \)；每次用 Bellman-Ford 或 SPFA 计算一次从 \( s \) 出发的最短距离 \( dist(v) \)，然后更新 \( p(v) := p(v) + dist(v) \)。调整后的边成本 \( w_ p'(u,v) = w(u,v) + p(u) - p(v) \) 可证明非负，之后便可用 Dijkstra 算法。这是算法中的关键优化技巧。 3. 增广 ： 找到最短路径后，设该路径的残量容量最小值为 \( \Delta \)（即瓶颈容量），实际可推送流量为 \( \min(\Delta, D - F) \)。沿路径更新残量网络中的容量（正向边减流量，反向边加流量），并更新当前总流量 \( F \) 和总成本。 4. 重复 ： 重复步骤 2–3，直到 \( F = D \)（即达到所需总流量）。如果中途无法再找到从 \( s \) 到 \( t \) 的路径，说明无可行流。 第五步：算法正确性直观理解 这个算法实际上是在模拟“连续贪心”策略：每次增加一单位流量时，都选择当前最便宜的路径。由于成本是线性的（单位成本固定），且没有负环（否则可无限降低成本，无有限最优解），这个贪心策略能保证最终得到最小成本流。数学上，这等价于在每一步保持“互补松弛条件”，最终到达最优解。 第六步：时间复杂度 每次增广至少增加 1 单位流量，最多增广 \( D \) 次。 每次找最短路径：若用 SPFA（容许负边），为 \( O(VE) \)；若用势函数+Dijkstra，为 \( O(E \log V) \)。 总复杂度：若用势函数+Dijkstra，为 \( O(D \cdot E \log V) \)。当 \( D \) 很大时可能较慢，但实践中常通过容量缩放（Capacity Scaling）优化，每次沿最短路径推送尽可能大的流量，减少增广次数。 总结 最小成本流问题是一个典型的网络优化问题，Successive Shortest Path 算法通过连续寻找最小成本增广路径来逐步构建最优流。关键点包括：转化为单源单汇问题、维护残量网络、用势函数+Dijkstra 高效求最短路径。这个算法是许多实际运输与调度问题的核心解法。