2023-06-25-最小费用最大流
一个重要的定理(Negative Cycle Optimality Conditions):一个流的费用是最小的(在大小相同的流之中),当且仅当它对应的残量网络中不存在负环。
正方向是显然的,反方向不好证明,本文暂时略过。
由这个定理,我们可以得到负环消去算法:先找到一个最大流,然后不停地找负环,沿负环增广,直到没有负环为止。
但是更常见的算法是 SSP (Successive Shortest Path) 算法,也就是把EK算法中的bfs换成SPFA。要证明这个算法的正确性,我们需要证明算法过程中不会产生负环。
欲证明:如果一个残量图中没有负环,那么经过一条最短路增广之后不会产生负环
证明:
使用反证法。
假设沿最短路
Q.E.D