最小费用最大流 (Minimum-Cost Maximum-Flow / MCMF)¶
在网络流中，最小费用最大流（MCMF） 问题是指在从源点 \(S\) 到汇点 \(T\) 的所有可行最大流中，寻找使得总费用最小的一种流方案。
网络中的每条有向边 \(e = (u, v)\) 包含两个关键属性：
- 容量 \(c(e) \ge 0\)：该边允许通过的最大流量。
- 单位费用 \(w(e)\)：每通过 1 个单位流量所产生的费用。
若边 \(e\) 实际通过的流量为 \(f(e)\)，则全图的总费用定义为：
\[
\text{Cost} = \sum_{e \in E} f(e) \cdot w(e)
\]
残量网络的费用性质¶
对于一条实际承载流量 \(f(e)\) 的边 \(e = (u, v)\)：
- 正向边 \((u, v)\)：残量容量为 \(c(e) - f(e)\)，单位费用为 \(+w(e)\)。
- 反向边 \((v, u)\)：残量容量为 \(f(e)\)，单位费用为 \(-w(e)\)（退回流量相当于撤销原边费用，实现“退费”）。
费用流最优性定理：一个可行流是同流量下费用最小的流，当且仅当其对应的残量网络中不存在负费用有向环。
1. 连续最短路算法 (基于 SPFA 的增广路 / Edmonds-Karp)¶
连续最短路算法（Successive Shortest Path）的核心思想是贪心增广：
- 在残量网络中，以边权为费用 \(w\)，使用 SPFA 寻找从源点 \(S\) 到汇点 \(T\) 的最短路径（处理反向边的负费用）。
- 若汇点 \(T\) 可达，求出该最短路径上的瓶颈容量 \(\Delta = \min_{(u, v) \in P} (c_{uv} - f_{uv})\)。
-
沿该路径增广流量 \(\Delta\)，更新各边及反向边的残量容量，并累加总费用：
\[ \text{总流量} \mathrel{+}= \Delta, \quad \text{总费用} \mathrel{+}= \Delta \cdot dist[T] \] -
重复上述过程，直到残量网络中汇点 \(T\) 不再可达（无增广路）。
复杂度¶
- 时间复杂度：最坏情况下为 \(\mathcal{O}(F \cdot V E)\)（\(F\) 为最大流值）。在竞赛随机或分层网络中，SPFA 常数极小、收敛极快，能稳定处理 \(V \le 5000, E \le 50000\) 的常见规模。
- 空间复杂度：\(\mathcal{O}(V + E)\)。
C++ 模板 (SPFA)¶
#include <vector>
#include <queue>
#include <algorithm>
#include <limits>
template <typename Flow = long long, typename Cost = long long>
struct MCMF_SPFA {
struct Edge {
int to;
Flow cap;
Flow flow;
Cost cost;
int rev;
};
int n, s, t;
std::vector<std::vector<Edge>> adj;
std::vector<Cost> dist;
std::vector<int> prev_v, prev_e;
std::vector<bool> in_queue;
static constexpr Cost INF_COST = std::numeric_limits<Cost>::max() / 2;
static constexpr Flow INF_FLOW = std::numeric_limits<Flow>::max() / 2;
MCMF_SPFA(int n, int s, int t)
: n(n), s(s), t(t), adj(n), dist(n), prev_v(n), prev_e(n), in_queue(n) {}
void add_edge(int from, int to, Flow cap, Cost cost) {
adj[from].push_back({to, cap, 0, cost, (int)adj[to].size()});
adj[to].push_back({from, 0, 0, -cost, (int)adj[from].size() - 1});
}
bool spfa() {
std::fill(dist.begin(), dist.end(), INF_COST);
std::fill(in_queue.begin(), in_queue.end(), false);
std::queue<int> q;
dist[s] = 0;
q.push(s);
in_queue[s] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
in_queue[u] = false;
for (int i = 0; i < (int)adj[u].size(); ++i) {
const auto &e = adj[u][i];
if (e.cap - e.flow > 0 && dist[u] + e.cost < dist[e.to]) {
dist[e.to] = dist[u] + e.cost;
prev_v[e.to] = u;
prev_e[e.to] = i;
if (!in_queue[e.to]) {
q.push(e.to);
in_queue[e.to] = true;
}
}
}
}
return dist[t] != INF_COST;
}
// 返回 {最大流, 最小费用}
std::pair<Flow, Cost> solve() {
Flow max_flow = 0;
Cost min_cost = 0;
while (spfa()) {
Flow bottleneck = INF_FLOW;
for (int v = t; v != s; v = prev_v[v]) {
const auto &e = adj[prev_v[v]][prev_e[v]];
bottleneck = std::min(bottleneck, e.cap - e.flow);
}
for (int v = t; v != s; v = prev_v[v]) {
auto &e = adj[prev_v[v]][prev_e[v]];
e.flow += bottleneck;
adj[v][e.rev].flow -= bottleneck;
}
max_flow += bottleneck;
min_cost += bottleneck * dist[t];
}
return {max_flow, min_cost};
}
};
2. Primal-Dual 算法 (Johnson 势能优化 + Dijkstra)¶
SPFA 虽然实现简练，但在极端构造数据下可能退化为单次 \(\mathcal{O}(VE)\) 甚至被卡常。
若能使用堆优化的 Dijkstra 算法（\(\mathcal{O}(E \log V)\)），效率将极大提升。但残量网络中存在费用为 \(-w\) 的反向边，直接运行 Dijkstra 并不合法。
借助 Johnson 势能法（Node Potentials） 消除负权边：
- 为每个节点 \(u\) 赋予一个势能 \(h[u]\)。
-
定义边 \((u, v)\) 在势能下的折减费用（Reduced Cost） 为：
\[ w'(u, v) = w(u, v) + h[u] - h[v] \] -
沿任意一条 \(S \to T\) 路径 \(P\) 的折减费用总和为：
\[ \sum_{(u, v) \in P} w'(u, v) = \sum_{(u, v) \in P} \big(w(u, v) + h[u] - h[v]\big) = \text{原总费用} + h[S] - h[T] \]由于 \(h[S] - h[T]\) 仅与端点势能有关、对所有 \(S \to T\) 路径完全恒定，因此在折减费用 \(w'\) 下的最短路径，等价于原费用 \(w\) 下的最短路径。
势能的维护与更新¶
- 初始势能：若初始网络无负权边，可直接设 \(h[u] = 0\)；若存在初始负权，可先运行一次 SPFA 初始化 \(h\)。
- 每次增广更新：
- 运行 Dijkstra 计算基于折减费用的最短距离 \(dist[u]\)；
- 更新势能：\(h[u] \leftarrow h[u] + dist[u]\)；
- 根据三角不等式 \(dist[u] + w'(u, v) \ge dist[v]\)，展开即得：\(w(u, v) + (h[u] + dist[u]) - (h[v] + dist[v]) \ge 0\)；
- 因此，所有残量边（包含新增的反向边）在更新后的折减费用依然严格非负，保证了下一次增广可继续安全使用 Dijkstra！
复杂度与工业界标准¶
- 时间复杂度：\(\mathcal{O}(F \cdot E \log V)\)（若含初始负权边则为 \(\mathcal{O}(V E + F \cdot E \log V)\)）。
- 竞赛工业级实现：AtCoder 官方算法库（
atcoder::mcf_graph）采用的正是本算法。
C++ 模板 (Primal-Dual Dijkstra)¶
#include <vector>
#include <queue>
#include <algorithm>
#include <limits>
template <typename Flow = long long, typename Cost = long long>
struct MCMF_Dijkstra {
struct Edge {
int to;
Flow cap;
Flow flow;
Cost cost;
int rev;
};
int n, s, t;
std::vector<std::vector<Edge>> adj;
std::vector<Cost> h; // 节点势能
std::vector<Cost> dist; // 折减距离
std::vector<int> prev_v, prev_e;
static constexpr Cost INF_COST = std::numeric_limits<Cost>::max() / 2;
static constexpr Flow INF_FLOW = std::numeric_limits<Flow>::max() / 2;
MCMF_Dijkstra(int n, int s, int t)
: n(n), s(s), t(t), adj(n), h(n, 0), dist(n), prev_v(n), prev_e(n) {}
void add_edge(int from, int to, Flow cap, Cost cost) {
adj[from].push_back({to, cap, 0, cost, (int)adj[to].size()});
adj[to].push_back({from, 0, 0, -cost, (int)adj[from].size() - 1});
}
// 若原图初始包含负权边，在建图后调用一次初始化势能
void init_potentials_spfa() {
std::fill(h.begin(), h.end(), INF_COST);
std::vector<bool> in_queue(n, false);
std::queue<int> q;
h[s] = 0;
q.push(s);
in_queue[s] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
in_queue[u] = false;
for (const auto &e : adj[u]) {
if (e.cap > 0 && h[u] + e.cost < h[e.to]) {
h[e.to] = h[u] + e.cost;
if (!in_queue[e.to]) {
q.push(e.to);
in_queue[e.to] = true;
}
}
}
}
}
bool dijkstra() {
std::fill(dist.begin(), dist.end(), INF_COST);
using Pair = std::pair<Cost, int>;
std::priority_queue<Pair, std::vector<Pair>, std::greater<Pair>> pq;
dist[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
for (int i = 0; i < (int)adj[u].size(); ++i) {
const auto &e = adj[u][i];
if (e.cap - e.flow > 0) {
Cost reduced_cost = e.cost + h[u] - h[e.to];
if (dist[u] + reduced_cost < dist[e.to]) {
dist[e.to] = dist[u] + reduced_cost;
prev_v[e.to] = u;
prev_e[e.to] = i;
pq.push({dist[e.to], e.to});
}
}
}
}
return dist[t] != INF_COST;
}
// 返回 {最大流, 最小费用}
std::pair<Flow, Cost> solve() {
Flow max_flow = 0;
Cost min_cost = 0;
while (dijkstra()) {
// 累加势能
for (int i = 0; i < n; ++i) {
if (dist[i] != INF_COST) {
h[i] += dist[i];
}
}
Flow bottleneck = INF_FLOW;
for (int v = t; v != s; v = prev_v[v]) {
const auto &e = adj[prev_v[v]][prev_e[v]];
bottleneck = std::min(bottleneck, e.cap - e.flow);
}
for (int v = t; v != s; v = prev_v[v]) {
auto &e = adj[prev_v[v]][prev_e[v]];
e.flow += bottleneck;
adj[v][e.rev].flow -= bottleneck;
}
max_flow += bottleneck;
// 增广路径的实际原费用等于 bottleneck * h[t]
min_cost += bottleneck * h[t];
}
return {max_flow, min_cost};
}
};
经典建模范式与转化技巧¶
1. 二分图最小权匹配 / 指派问题¶
- 问题：将 \(N\) 个任务分配给 \(N\) 名工人，成本矩阵为 \(C_{ij}\)，求匹配的总最小开销。
- 网络构建：
- 源点 \(S \to \text{工人 } i\)：容量 \(1\)，费用 \(0\)。
- 工人 \(i \to \text{任务 } j\)：容量 \(1\)，费用 \(C_{ij}\)。
- 任务 \(j \to \text{汇点 } T\)：容量 \(1\)，费用 \(0\)。
- 求出的最小费用最大流的费用值即为最优指派开销。
2. 最大费用最大流¶
- 若题目要求收益最大化（最大费用）：
- 将全图所有边的费用取相反数：\(w'(e) = -w(e)\)；
- 使用支持负权的费用流算法求解最小费用流；
- 最终最大收益即为 \(-\text{min\_cost}\)。
- (注意：前提是原图在正费用下不包含正环，否则最大流将无界)。
3. \(K\) 条不相交最短路径¶
- 问题：在网络中选取 \(k\) 条点不相交（或边不相交）的路径，使得边权和最小。
- 拆点技术（点不相交约束）：
- 每个节点 \(u\) 拆为入点 \(u_{in}\) 与出点 \(u_{out}\)；
- 连边 \(u_{in} \to u_{out}\)，容量为 \(1\)（源点/汇点容量为 \(k\)），费用为 \(0\)；
- 对原图有向边 \((u, v)\)（长为 \(w\)），连边 \(u_{out} \to v_{in}\)，容量为 \(1\)，费用为 \(w\)；
- 限制流量为 \(k\)，跑费用流。
4. 多重容量约束的区间/线段选择问题¶
- 问题：给定若干区间 \([l_i, r_i]\)，选定可获得收益 \(W_i\)。要求数轴上任意位置被覆盖的次数不超过 \(K\)，求最大收益。
- 连续时间轴网络转化：
- 离散化所有端点构成有序轴 \(t_1 < t_2 < \dots < t_m\)；
- 建立骨干基准链：相邻节点 \(t_i \to t_{i+1}\) 连边，容量为 \(K\)，费用为 \(0\)；
- 对每个区间 \([l_j, r_j]\)（权值 \(W_j\)），连边 \(l_j \to r_j\)，容量为 \(1\)，费用为 \(-W_j\)；
- 超级源点 \(S \to t_1\)（容量 \(K\)，费用 0），\(t_m \to T\)（容量 \(K\)，费用 0）。
经典推荐习题¶
-
提示
SPFA 增广路与 Primal-Dual Dijkstra 双模板的标准评测靶场。累加总费用时务必使用
long long防止溢出。 -
CSES 2130 - Distinct Routes II
提示
求图中 1 到 \(n\) 的 \(k\) 条边不相交最短路径，总长最小。
- 原图每条边容量设为 1，费用设为 1。
- 超级源点 \(S \to 1\) 容量为 \(k\)，费用为 0。
- 运行费用流。若最大流 \(< k\) 则输出
-1。 - 从源点开始，沿有实际正向流量 \(f(e) = 1\) 的边使用 DFS 追踪即可复原出这 \(k\) 条完整路径。
-
Codeforces 277E - Binary Tree on Plane
提示
平面上有 \(n\) 个点，选择若干有向边构成一棵二叉树，根节点无父节点，其余每个点入度为 1（恰有一个父节点），且出度至多为 2（至多两个子节点）。边只能从 \(y\) 坐标严格较高的点连向较低的点，边权为欧几里得几何距离。
- 拆点：将每个点 \(i\) 拆为 \(i_{in}\)（接收父节点连边）与 \(i_{out}\)（作为父节点发出子边）。
- 源点 \(S \to i_{out}\) 容量 2，费用 0；\(i_{in} \to T\) 容量 1，费用 0。
- 对所有 \(y_i > y_j\) 的点对，连边 \(i_{out} \to j_{in}\)，容量 1，费用 \(\text{dist}(i, j)\)。
- 跑 MCMF。若最大流为 \(n - 1\) 则输出最小费用，否则说明无法构成完整二叉树输出
-1。
-
AtCoder ABC 247 G - Dream Team
提示
选拔 \(k\) 名学生，要求大学编号互不相同且专业赛道互不相同，总能力值最大。对所有合法的 \(k \in [1, \min(|A|, |B|)]\) 分别求解。
- 建立二分图：大学集合 \(A\) 与赛道集合 \(B\)。
- 源点 \(S \to A_i\) 容量 1 费用 0；\(B_j \to T\) 容量 1 费用 0。
- 候选学生 \((A_i, B_j)\) 连边：容量 1，费用 \(10^9 - C\)。
- 每次增广 1 单位流量，步数 \(k\) 的最大答案即为 \(k \cdot 10^9 - \text{min\_cost}\)。当不存在增广路时终止。
-
提示
选取至多 4 条不相交子序列路径，每条路径相邻两项数值相差 1 或模 7 同余，最大化所包含的元素总数。
- 拆点限流：每个元素拆为入点与出点，容量为 1，费用为 \(-1\)。
- 利用模 7 辅助点与前驱相同值辅助点，将直接连边数量从 \(\mathcal{O}(N^2)\) 优化至 \(\mathcal{O}(N)\)。
- 从超级源点向汇点推流 4 单位流量，最小费用的相反数即为最多可选元素个数。