费用流

概述

给定一个网络 $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\limits_{(s,v) \in E}f(s,v)$ 的前提下最小化 $\sum\limits_{(u,v) \in E}f(u,v) \times w(u,v)$。

模板题：Luogu B3608（$n \le 400$，$m \le 15000$，答案小于 $2^{31}$，数据较弱，不存在最小费用最大流的极限情况）、Luogu P3381（$n \le 5 \times 10^3$，$m \le 5 \times 10^4$，答案小于 $2^{31}$，卡 EK，数据随机生成）、UOJ 487（$1 \le n,m \le 500$，容量在 $[1,10^9]$ 内，费用在 $[-2 \times 10^6,2 \times 10^6]$，存在负圈，数据较强）。

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 算法求解最短路，该网络的最大流为 $f$，则最坏时间复杂度为 $O(nmf)$，这是伪多项式的。

代码实现

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

基于 EK 算法的实现

提交记录 备份

基于 Dinic 算法的实现

提交记录 备份

基于 Capacity Scaling 的弱多项式复杂度最小费用流算法

例题：费用流与二分图带权匹配

例题：费用流与不等式差分模型

例题：费用流与最小链覆盖

例题

参考资料

• 坐井观天 : 从入门到精通: 最小费用流的“zkw算法”
• 基于 Capacity Scaling 的弱多项式复杂度最小费用流算法 - ouuan的博客