我的算法书 - 最小费用最大流

一句话算法

最小费用最大流就是每次在残量网络里找一条费用最小的增广路，先把流量做到最大，再让总费用尽量小。

问题模型

给定一个有向网络 $G=(V,E)$ 。每条边 $(u,v)$ 有两个属性：

容量 $c(u,v)$ ：这条边最多能通过多少流量。
单位费用 $w(u,v)$ ：每通过 $1$ 单位流量要付出的费用。

如果边 $(u,v)$ 上实际流量为 $f(u,v)$ ，则这条边贡献的费用是：

f(u,v)\cdot w(u,v)

目标是从源点 $S$ 向汇点 $T$ 发送尽可能多的流量，并在最大流量的前提下，让总费用最小。

“最小费用最大流”

在所有最大流中，总费用最小的那一个流，称为最小费用最大流。

注意顺序：先最大流，再最小费用。不是为了少花钱而主动少送流。

核心直觉

普通最大流只关心“还能不能送更多流”。费用流还要关心“这次送流走哪条路最便宜”。

因此我们在残量网络里做两件事：

找一条从 $S$ 到 $T$ 的最短路，边权是费用。
沿着这条路尽量增广。

反向边是费用流的关键。若正向边费用为 $w$ ，反向边费用必须是 $-w$ 。

它表示：如果后面发现之前的选择不够好，可以沿反向边把这段流退回去，同时退回之前支付的费用。

残量网络

对每条原始边：

u -> v, capacity = cap, cost = cost

建两条边：

u -> v, capacity = cap, cost = cost
v -> u, capacity = 0,   cost = -cost

当沿 $u\to v$ 推送 f 单位流量后：

正向边剩余容量减少 f。
反向边剩余容量增加 f。

如果以后走反向边 $v\to u$ ，就等价于撤销之前在 $u\to v$ 上的一部分流量。

算法步骤

SPFA 版最小费用最大流的步骤：

建立残量网络，每条边加一条费用相反的反向边。
在残量网络中，用 SPFA 找从 $S$ 到 $T$ 的最短费用路。
若找不到路，说明不能继续增广，算法结束。
沿最短路找到可增广的最小剩余容量 pushed。
总流量增加 pushed。
总费用增加：

$pushed\times dist[T]$
沿路径更新正向边和反向边容量。
回到第 2 步。

算法证明

为什么反向边费用是负数

如果之前沿 $u\to v$ 推了 $1$ 单位流，费用增加 $w$ 。

后来沿反向边 $v\to u$ 退回 $1$ 单位流，本质上是撤销之前的选择，所以费用应该减少 $w$ 。

因此反向边费用必须是：

-w

这样残量网络里的路径费用变化，才和真实总费用变化一致。

为什么每次找最短增广路

关键不变量：当前流量大小固定时，算法维护的是该流量下费用最小的流。

从当前流量增加到更大流量时，需要在残量网络中找一条增广路。残量网络中一条路径的费用，正好表示“把当前流改造成新流时，总费用的增量”。

选择最短增广路，就是选择当前这次增加流量的最小费用增量。

反向边允许路径撤销之前的局部选择，因此算法不只是贪心固定旧路径，而是在残量网络中重新调整整个流。

当残量网络中不存在 $S\to T$ 路径时，最大流已经达到。由于每次都选择最小费用增量，并且反向边允许修正旧流，最终得到最大流中的最小费用方案。

复杂度分析

设点数为 $n$ ，边数为 $m$ ，最大流量为 $F$ 。

SPFA 每次最坏 $O(nm)$ ，每轮至少增广 $1$ 单位流量，所以粗略上界为：

O(Fnm)

实际竞赛中，SPFA 版容易写、能处理负费用边，但在大数据上可能被卡。更稳定的做法是使用势能函数把费用重标号，再用 Dijkstra 找最短路。

本文代码选择 SPFA 版作为入门模板。

代码实现

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

        #include <bits/stdc++.h>
using namespace std;

struct MinCostMaxFlow {
    struct Edge {
        int to;
        int rev;
        int cap;
        int cost;
    };

    static constexpr int INF = 1e9;
    int n;
    vector<vector<Edge>> g;
    vector<int> dist, prev_v, prev_e;

    explicit MinCostMaxFlow(int n) : n(n), g(n + 1), dist(n + 1), prev_v(n + 1), prev_e(n + 1) {}

    void add_edge(int from, int to, int cap, int cost) {
        Edge forward{to, (int)g[to].size(), cap, cost};
        Edge backward{from, (int)g[from].size(), 0, -cost};
        g[from].push_back(forward);
        g[to].push_back(backward);
    }

    bool spfa(int s, int t) {
        fill(dist.begin(), dist.end(), INF);
        vector<bool> in_queue(n + 1, false);
        queue<int> q;

        dist[s] = 0;
        in_queue[s] = true;
        q.push(s);

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            in_queue[u] = false;

            for (int i = 0; i < (int)g[u].size(); ++i) {
                const Edge &e = g[u][i];
                if (e.cap <= 0) continue;
                if (dist[e.to] > dist[u] + e.cost) {
                    dist[e.to] = dist[u] + e.cost;
                    prev_v[e.to] = u;
                    prev_e[e.to] = i;
                    if (!in_queue[e.to]) {
                        in_queue[e.to] = true;
                        q.push(e.to);
                    }
                }
            }
        }

        return dist[t] != INF;
    }

    pair<int, int> min_cost_max_flow(int s, int t) {
        int flow = 0;
        int cost = 0;

        while (spfa(s, t)) {
            int pushed = INF;
            for (int v = t; v != s; v = prev_v[v]) {
                const Edge &e = g[prev_v[v]][prev_e[v]];
                pushed = min(pushed, e.cap);
            }

            flow += pushed;
            cost += pushed * dist[t];

            for (int v = t; v != s; v = prev_v[v]) {
                Edge &e = g[prev_v[v]][prev_e[v]];
                e.cap -= pushed;
                g[v][e.rev].cap += pushed;
            }
        }

        return {flow, cost};
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s, t;
    cin >> n >> m >> s >> t;

    MinCostMaxFlow solver(n);
    for (int i = 0; i < m; ++i) {
        int u, v, cap, cost;
        cin >> u >> v >> cap >> cost;
        solver.add_edge(u, v, cap, cost);
    }

    auto [flow, cost] = solver.min_cost_max_flow(s, t);
    cout << flow << ' ' << cost << '\n';
    return 0;
}

测试用例

输入：

含义：

源点 1，汇点 4。
每条边格式为 u v cap cost。

输出：

2 8

解释：

最终发送 2 单位流量。两条实际路径可以看作：

1 -> 2 -> 4, cost = 3 + 1 = 4
1 -> 3 -> 4, cost = 1 + 3 = 4

总费用为 8。

反悔机制示例

还是上面的图：

1 -> 2 cost 3
1 -> 3 cost 1
2 -> 3 cost 1
2 -> 4 cost 1
3 -> 4 cost 3

如果第一轮选择了：

1 -> 3 -> 2 -> 4

费用是：

1+1+1=3

这看起来很便宜，但它占用了中间边。

第二轮残量网络可能选择：

1 -> 2 -> 3 -> 4

其中 $2\to3$ 是上一轮 $3\to2$ 的反向边，费用为 $-1$ 。

第二轮增量费用：

3+(-1)+3=5

两轮合并后，中间的 $3\to2$ 与 $2\to3$ 抵消，实际变成：

1 -> 2 -> 4
1 -> 3 -> 4

总费用：

3+5=8

这说明反向边不是“多出来的奇怪边”，而是算法自动修正旧决策的工具。

应用分类详解

费用流的本质是“带容量限制的最优分配”。只要题目既有流量/匹配/分配约束，又有代价最小或收益最大，就应该考虑费用流。

一、带费用的最大匹配

典型模式： 左边对象匹配右边对象，每个匹配有代价或收益。

识别信号： 工人分配任务、学生分配宿舍、二分图匹配加权。

核心建模： 源点连左部，右部连汇点，中间边容量为 1，费用为匹配代价。

二、多商品分配

典型模式： 若干供应点向需求点运输，每条运输线路有单位成本。

识别信号： 仓库、工厂、运输、供给量、需求量、最小总成本。

核心建模： 源点连供应点，供应点连需求点，需求点连汇点。

三、路径选择与边不重复

典型模式： 要选若干条路径，边或点容量有限，总代价最小。

识别信号： 两条不相交路径、每条边只能用一次、总长度最短。

核心建模： 边容量限制可使用次数，费用为路径长度。

四、最大收益模型

典型模式： 在容量限制下最大化收益。

识别信号： 最大利润、最大收益、选择若干交易。

核心建模： 把收益取负，求最小费用；或改成最大费用最大流。

经典例题

1. 最小费用最大流模板

luogu-P3381

直接使用本文模板，输入边为容量和费用，输出最大流和最小费用。

2. 运输问题

多个仓库向多个商店供货，每条线路有运输成本。供给和需求都可以转成容量，运输成本转成费用。

3. 带权二分图匹配

每个左部点最多匹配一个右部点，每条匹配边有代价。用费用流可以处理“必须匹配尽量多，且总费用最小”的版本。

参考

本书最大流 Edmonds-Karp：graph/netflow/ek/index.md
本书 Dinic：graph/网络流/dinic/index.md
ZKW 费用流旧笔记：graph/网络流/费用流/zkw.md