基于 Capacity Scaling 的弱多项式复杂度最小费用流算法
hack 常见的费用流算法
前置知识
一些定义
将最小费用最大流问题转化为无源汇最小费用流问题
负环
节点势能 & 边的 reduced cost
capacity scaling
给一条边的容量加一
防止溢出
流程总结
关于 SPFA
关于出题
大多数人所使用的费用流算法,即每次求出残量网络中 $s$ 到 $t$ 关于费用的最短路进行增广(将 Dinic 最大流算法中的 BFS 改为 SPFA),是伪多项式复杂度的,最坏情况下复杂度为 $O(nmf)$,其中 $f$ 为最大流.已知有一种在点数为 $n$,边数为 $O(n^2)$,值域为 $O(