基于Floyd算法的最小费用流的负回路算法（图解）

屈婉玲《算法设计与分析》第2版第7章网络流算法学习笔记。

概述

最小费用流问题，可视为一般化的最短路径问题和最大流问题，即只要选定合适的权重、容量、流量，解决最小费用流的方法就能用来解决上述问题。另一方面，也意味着解最小费用流问题至少和解最短路径或最大流问题一样难。

显然可以用来解决物流运输最小成本问题，除此之外还有广泛应用，比如劳动力分配问题：

劳动力和任务间用边连接，费用为工人对任务的讨厌程度（当不可能干某任务时可以是∞），流量是完成任务需要的小时数。

定义

容量-费用网络：N={V, E, c, w, s, t}
在容量网络N={V, E, c, s, t}中，添加单位费用w，将其称作容量-费用网络。

费用：w(f)
设f是N上的一个可行流，w(f)=∑ w(i, j) * f(i, j) 为f的费用。

流量v0的最小费用流：
给定流量v0的可行流中，费用最小的称作流量v0的最小费用流。

算法思想

先任意找出一个流量为v0的可行流。如何找呢？利用最大流算法，找出最大流f，若v(f)<v0，最大流量都达不到v0，说明无解；若v(f)>=v0，只需将v(f)修剪成与v0相等即可。

接下来构造残余容量网络：前向边的残余容量为c - f，后向边的残余容量为f；