网络流学习笔记（3）：最小费用流
根据网络流相关的知识，可以以计算机为顶点，通信电缆为边，从而得到一个有向图，每条边都有容量和费用。题目可以理解为，保证从到有流量为的流的前提下，使得费用最小。
这就是在最大流问题的网络中，给边新加上了费用，而求的不再是流量的最大值，而是流量为F 时费用的最小值。这类问题叫做最小费用流问题。
接下来，让我们来考虑一下这类问题的解法。求解最大流时，我们在残余网络上不断贪心地增广而得到了最大流。现在边上多了费用，如果我们在残余网络上总是沿着最短路增广又如何呢？此时，残余网络中的反向边的费用应该是原边费用的相反数，以保证过程是可逆而正确的。因为有
负权边，所以就不能用 Dijkstra算法求最短路了，而需要用Bellman-Ford算法。