求解最小费用流的算法有很多，如增广路算法(SPFA)，消圈算法，zkw 算法，Primal Dual 算法及网络单纯形，其中消圈算法和网络单纯形较为通用但速度不够快或编程复杂度过高，SPFA 和 zkw 在不同的图上各有所长，这里介绍不容易被卡掉的 Primal Dual 算法。
注意: Primal Dual 算法也不能适用于存在负圈的图。
思想
实际上我们算法的核心仍然是交替的进行最短路与最大流操作。
定义
势
势指的是给每个顶点赋予一个新的标号 $h(v)$，在这个势的基础上，将边 $e = (u, v)$，的长度变为 $d’(e) = d(e) + h(u) - h(v)$，于是从 $d’$ 中的 $s-t$ 路径的长度中减去常数 $h(s) - h(t)$ 就得到了 $d$ 中对应路径的长度，因此 $d’$ 中的最短路也就是 $d$ 中的最短路。
因此,合理的选取势,使得对所有的 $e$ 都有 $d'(e) \geq 0$ 的话，我们就可以在 $d’$ 中用 Dijkstra 算法求最短路,从而得到 $d$ 的最短路。
对于不含负圈的图,我们可以通过选取 $h(v) = (s$ 到 $v$ 的最短距离$)$ 来做到 $d'(e) \geq 0$。
因为对于边 $e = ( u , v )$ 有:
因此 $d'( e ) = d ( e ) + h ( u ) - h ( v ) \geq 0$
下面来考虑如何依次更新流量为 $i$ 时的最小费用流 $f_i$ 以及其所对应的势 $h_i$ 。首先我们定义以下变量:
- $f_i ( e )$ : 流量为 $i$ 的最小费用流中边 $e$ 的流量
- $h_i ( v )$ : $f_i$ 的残量网络中 $s$ 到 $v$ 的最短距离
- $d_i ( e )$ : 考虑势 $h_i$ 后边 $e$ 的长度
实现
初始化
若原图不含负圈,则我们可以将 $f_i (e )$ 初始化为 $0$，若原图也不存在负权边，那么我们还可以直接用 Dijkstra 计算 $h$，否则我们先使用 SPFA 计算 $h$，再使用 Dijkstra 计算 $d$。
增广
求得 $f_i$ 与 $h_i$ 后,我们沿着 $f_i$ 的残量网络中 $s$ 到 $t$ 的最短路增广,我们就得到了 $f_{i + 1}$,而这步可以借助 $h_i$，找到那些只经过 $d_i( e ) = 0$ 的边的路径进行增广(这些边一定在最短路上)．
而为了求 $h_{i + 1}$, 我们需要求 $f_{i + 1}$ 的残量网络上的最短路。考虑 $f_{i + 1}$ 的残量网络中的边 $e = ( u , v )$ 。如果 $e$ 也是 $f_i$ 的残量网络中的边的话,那么根据 $h$ 的定义有 $d_i ( e ) \geq 0$。如果 $e$ 不是 $f_i$ 的残量网络中的边的话,那么 $rev (e )$ 一定是 $f_i$ 的残量网络中 $s$ 到 $t$ 的最短路中的边,所以有 $d_i ( e ) = - d_i ( rev ( e )) = 0$。综上, $f_{i + 1}$ 的残量网络中的所有边 $e$ 满足 $d_i ( e ) \geq 0$,因而可以用 Dijkstra 算法求最短路。
时间复杂度
当原图不存在负权时，我们直接使用优先队列优化 Dijkstra 算法，此时 Primal Dual 算法的复杂度为 $O(f \cdot (V + E) \log V)$，若使用斐波那契堆优化，复杂度降为 $O(f \cdot (E + V \log V))$。
当原图存在负权时，我们先使用 SPFA 计算 $h$，再使用 Dijkstra 算法，此时 Primal Dual 算法的复杂度为 $O(VE + f \cdot (V + E) \log V)$，若使用斐波那契堆优化，复杂度降为 $O(VE + f \cdot (E + V \log V))$。
代码
使用 pb_ds 中的优先队列优化，复杂度为 $O(VE + f \cdot (E + V \log V))$，若没有负权，自行去掉 SPFA，同时使 $h$ 的初始值为 $0$。
1 | /* |
