费用流

关注
费用流www.shan-machinery.com  费用流

在看这篇文章前请先看 网络流简介 这篇 wiki 的定义部分。

费用流¶

给定一个网络G=(V,E) ,每条边除了有容量限制c(u,v) ,还有一个单位流量的费用w(u,v) 。

当(u,v)的流量为f(u,v)时,需要花费f(u,v)\times w(u,v) 的费用。

w也满足斜对称性,即w(u,v)=-w(v,u) 。

则该网络中总花费最小的最大流称为 最小费用最大流,即在最大化\sum_{(s,v)\in E}f(s,v) 的前提下最小化\sum_{(u,v)\in E}f(u,v)\times w(u,v) 。

SSP 算法¶

SSP(Successive Shortest Path)算法是一个贪心的算法。它的思路是每次寻找单位费用最小的增广路进行增广,直到图上不存在增广路为止。

如果图上存在单位费用为负的圈,SSP 算法正确无法求出该网络的最小费用最大流。此时需要先使用消圈算法消去图上的负圈。

证明¶

我们考虑使用数学归纳法和反证法来证明 SSP 算法的正确性。

设流量为i的时候最小费用为f_i 。我们假设最初的网络上 没有负圈,这种情况下f_0=0。

假设用 SSP 算法求出的f_i是最小费用,我们在f_i的基础上,找到一条最短的增广路,从而求出f_{i+1} 。这时f_{i+1}-f_i是这条最短增广路的长度。

假设存在更小的f_{i+1} ,设它为f'_{i+1} 。因为f_{i+1}-f_i已经是最短增广路了,所以f'_{i+1}-f_i一定对应一个经过 至少一个负圈 的增广路。

这时候矛盾就出现了:既然存在一条经过至少一个负圈的增广路,那么f_i就不是最小费用了。因为只要给这个负圈添加流量,就可以在不增加s流出的流量的前提下,使f_i对应的费用更小。

综上,SSP 算法可以正确求出无负圈网络的最小费用最大流。

时间复杂度¶

如果使用 Bellman-Ford 算法 求解最短路,每次找增广路的时间复杂度为O(nm) 。设该网络的最大流为f ,则最坏时间复杂度为O(nmf) 。事实上,这个时间复杂度是 伪多项式的。

为什么 SSP 算法具有伪多项式时间复杂度?

一般所说的 多项式时间复杂度,要求算法花费的时间,可以表示为一个关于输入数据规模n的多项式函数。

而在 SSP 算法中,网络的最大流f并不一定能表示为关于图的点数n的多项式函数。事实上可以构造m=n^2,f=2^{n/2}的网络1,该情况下 SSP 算法的时间复杂度将达到O(n^3 2^{n/2}) 。这明显是指数时间复杂度。

实现¶

只需将 EK 算法或 Dinic 算法中找增广路的过程,替换为用最短路算法寻找单位费用最小的增广路即可。

基于 EK 算法的实现 1 2 3 4 5 6 7 8 910111213141516171819202122232425262728293031323334353637383940struct qxx {int nex, t, v, c;};qxx e[M];int h[N], cnt = 1;void add_path(int f, int t, int v, int c) {e[++cnt] = (qxx){h[f], t, v, c}, h[f] = cnt;}void add_flow(int f, int t, int v, int c) {add_path(f, t, v, c);add_path(t, f, 0, -c);}int dis[N], pre[N], incf[N];bool vis[N];bool spfa() {memset(dis, 0x3f, sizeof(dis));queue q;q.push(s), dis[s] = 0, incf[s] = INF, incf[t] = 0;while (q.size()) {int u = q.front();q.pop();vis[u] = 0;for (int i = h[u]; i; i = e[i].nex) {const int &v = e[i].t, &w = e[i].v, &c = e[i].c;if (!w || dis[v]dis[u] + cost[i]) {dis[v] = dis[u] + cost[i];if (!vis[v]) q.push(v), vis[v] = 1;}}}return dis[t] != INF;}int dfs(int u, int t, int flow) {if (u == t) return flow;vis[u] = 1;int ans = 0;for (int &i = cur[u]; i && ans https://www.shan-machinery.com