费用流 费用流 目录
SSP 算法
Primal-Dual 原始对偶算法
习题
在看这篇文章前请先看 网络流简介 这篇 wiki 的定义部分.
给定一个网络 ,每条边除了有容量限制 ,还有一个单位流量的费用 .
当 的流量为 时,需要花费 的费用.
也满足斜对称性,即 .
则该网络中总花费最小的最大流称为 最小费用最大流,即在最大化 的前提下最小化 .
SSP(Successive Shortest Path)算法是一个贪心的算法.它的思路是每次寻找单位费用最小的增广路进行增广,直到图上不存在增广路为止.
如果图上存在单位费用为负的圈,SSP 算法正确无法求出该网络的最小费用最大流.此时需要先使用消圈算法消去图上的负