费用流学习笔记

前面我们已经讲过了最大流和最小割，现在我们来讲费用流。

这个时候一条边不止有一个容量，还有一个费用。

这个费用表示的是某条边通过一个单位流量需要的费用。

而且，一个路径的费用求的不是最小值，而是总和。

我们要求的问题是这样的：给定一个预算，每一条边通过一个单位流量都有一个费用，也有一个通过流量上界，求在最大流前提下，总费用的最小值或者是最大值。

假设有这个图：

将橙色的字表示为容量，黄色字表示费用。

如果这个时候我们不考虑费用流，只考虑最大流，很容易发现这个图的最大流为 $4$。

这个时候我们有两种路径可以走，很显然下面更加便宜一点。（因为性价比比较高）

如果下面走了 $3$ 的流量，费用就是 $3\times (2+4+3)$。

最小费用最大流

假设我们现在有一个有向图，每条边有容量和单位流量费用。设源点为 $st$，汇点为 $ed$。

思考一下费用流的问题，发现这个问题不是很简单：有些增广路径虽然可以通过的流量很多，但是费用很高。而有些增广路径只能通过那么一点点流量，但是很便宜。而我们最终的目的就是达成最大流，是不是有点难以选择？

于是为了解决这个问题，我们需要做一个取舍：抛弃 Dinic 的优化版本，而是回归基本的 Ford - Fulkerson 这个算法来解决问题。

回忆一下 Ford - Fulkerson 算法的特点。发现其与 Dinic 的不同点就是不使用 bfs 进行优化，而是直接找任意长度的增广路径。

---

很容易发现 Ford - Fulkerson 对于所有的增广路都是“一视同仁”的，但是费用流和我要花费的钱有关，显然需要对增广路有一点点“区别对待”。

到底怎么区别对待呢？有没有想起来上面说过的一句话：

很显然下面更加便宜一点。（因为性价比比较高）

没错，性价比！！！

例如这个图里面的两条增广路径，我们显然会先选择下面的路径来逼近最终的最大流。因为对于两者来讲，同时通过 $1$ 的流量，上面的路径会花费 $3+4+2=9$ 的费用，而下面的路径会花费 $5+2=7$ 的费用。

于是得到以下结论：

对于两条 $st\to ed$ 的增广路径，记路径上面的边的通过单位流量的费用的和（因为这里码字和阅读都过于麻烦，这里就简称为“路径费用和”）分别为 $a_x,a_y$，则一定是先选择 $a$ 值更加小的来使目前的答案逼近最终的最大流，然后再选择 $a$ 值大的来逼近。

这下知道为什么不能是用 Dinic 来广搜分层了吧？因为你不能保证性价比最高的一定会被 Dinic 考虑到！！但是 Ford - Fulkerson 就很好，它会对于每一条增广路都考虑一遍，不会出现遗漏的情况。

那么，$st\to ed$ 的路径中，路径费用和最小的路径是什么呢？？？我们会不由自主地联想到一个东西：最短路。

我们可以把每一条边上面的单位流量费用来作为边权，这个时候 $st\to ed$ 的最短路显然就是先要考虑的路径。

虽然这个时候我们不能管你这条路径通过了多少流量，但是我们肯定保证你这条路径贡献的流量不能是 $0$，直接把容量将为 $0$ 的边忽略掉即可。

考虑完这个路径，我们就可以把这个路径上面的所有的边的容量都减去这条路径贡献的流量。

---

我们考虑正确性：这样贪心会不会造成捡了芝麻丢了西瓜的效果呢？

很容易发现，只要我们找的出来反例，这个算法 idea 就是假的了。

假设我们有这个图。

然后我们就会发现，我们能不能把中间那条费用为 $1,1,1$ 的路换到最下面的一条路径啊？？这样显然省的更多。

于是我们就找到了反例。

我们该怎么办呢？？

---

我们发现我们遗漏了一个也许有大用的东西：反悔贪心。

在 Ford - Fulkerson 算法假掉的时候，我们正是使用这个东西来把它纠正掉。

那么我们就想：能不能也在求费用流的时候也来建一下反边呢？

反边的容量和正边的容量是不变的，就是一开始输入是赋给的容量。

而因为反边相当于从正边退回去一些流量，所以其费用是正边的相反数。

这个时候就发现现在可以正确处理这个反例了！！！

但是我们还有一些无法挽救的点：因为存在了负权边，不能再使用 Dijkstra 算法了，需要使用 Bellman_Ford 或者是 spfa。

当然还是有一些东西可以跑 dijkstra，但是一定是加入了一些手法，一般的费用流问题不能是用 dijkstra 来解决。

---

那么现在问题就来到了负环的上面，既然有负权边就很有可能会有负环，而存在负环的图显然不存在最短路。

如果存在负环的话，那不就说明整个算法没有答案了？

但是对于网络流问题的话，负环并不是这样的。

举个例子，这样。

这个时候，走多次负环不会使问流量变优，实际上我们只需要走这个负环一次。

而且大多数网络流问题都一开始保证费用是 $\ge 0$，所以不需要担心负环的问题。

那么你可能会问：如果是反边构成一个负环呢？？？那么就对应下来就是正边权成了一个环。很显然走这个环不会更优，那我们就可以拿这个环不存在。

P3381 【模板】最小费用最大流

现在开始讲实现。

题意异常复杂，估计正常人没有心思来看看了也不一定看得懂。总之就是我前面讲的问题。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m, s, t;
const int N = 5010;struct edge {int to, val, c, id;//现在增加了一个东西 c，表示每条边的费用
};
vector<edge> v[N];void add(int x, int y, int w, int c) {v[x].push_back({y, w, c, (int)v[y].size()});v[y].push_back({x, 0, -c, (int)v[x].size() - 1});//连边
}
int dis[N];
int fr[N], idx[N];
bool f[N];void spfa(int st) {//spfa 算法memset(f, 0, sizeof f), memset(fr, -1, sizeof fr), memset(idx, 0, sizeof idx), memset(dis, 0x3f, sizeof dis);queue<int> q;q.push(st), f[st] = 1, dis[st] = 0;while (!q.empty()) {int u = q.front();q.pop(), f[u] = 0;int cnt = 0;for (auto [to, val, c, id] : v[u]) {if (val > 0 && dis[u] + c < dis[to]) {dis[to] = dis[u] + c, fr[to] = u, idx[to] = cnt;if (!f[to])f[to] = 1, q.push(to);}cnt++;}}
}void mxflow(int s, int t) {int ans = 0, f = 0;while (1) {spfa(s);if (dis[t] > 1e14) {//发现不可达了就说明现在已经没有 s 到 t 的增广路径cout << f << " " << ans << endl;exit(0);}int x = 9e18;for (int i = t; i != s; i = fr[i])x = min(x, v[fr[i]][idx[i]].val);//计算路径上面可以提取出来的流量f += x, ans += x * dis[t];//计算答案for (int i = t; i != s; i = fr[i])v[fr[i]][idx[i]].val -= x, v[i][v[fr[i]][idx[i]].id].val += x;//然后就更新正向边和反向边的容量即可}
}signed main() {cin >> n >> m >> s >> t;for (int i = 1; i <= m; i++) {int x, y, w, c;cin >> x >> y >> w >> c;add(x, y, w, c);}mxflow(s, t);return 0;
}

感觉这种方法有一点点慢……但是对于一般的 $n\le 5000,m\le 50000$ 还是能过的，所以不用担心。

所以费用流这东西一般都可以看作是 $O(n^2)$ 的，当然也会有一些毒瘤数据恰好卡网络流。

最小费用特定流

这个时候就变成了：给定一个预算，每一条边通过一个单位流量都有一个费用，也有一个通过流量上界，求在源点到汇点通过恰好 $k$ 的流前提下，总费用的最小值或者是最大值。

这个时候该如何处理呢？？？

不难观察到，原来我们最小费用最大流的 $k$ 就等于原图的最大流，所以最小费用最大流本身还是一个特定流问题。

所以考虑仿制最小费用最大流的写法。可以从 $k$ 每一次减去求出来的最短路径的容量最小值。

只需要改动一下 mxflow 的函数即可。

int mxflow(int s, int t, int k) {int ans = 0;while (k > 0) {spfa(s);if (dis[t] > 1e14) {//这里就无解了cout << "-1" << endl;exit(0);}int x = k;for (int i = t; i != s; i = fr[i])x = min(x, v[fr[i]][idx[i]].val);k -= x, ans += x * dis[t];for (int i = t; i != s; i = fr[i])v[fr[i]][idx[i]].val -= x, v[i][v[fr[i]][idx[i]].id].val += x;}return ans;
}