网络流可以根据是否有源汇，下界，最大最小或是可行流，是否有费用，是否有负权环划分成好几类，下面就来做一个总结。（注：以下只讨论最小费用，最大费用与此类似）

（以下仅是个人理解，仅供参考，若有错误，欢迎指出）

　　1.有源汇，无下界，最大流，无费用。

　　这个是最基础的，就不细讲了。

　　2.有源汇，无下界，最大流，有费用。

　　……

　　3.有源汇，无下界，最小流，无（有）费用。

　　……

　　4.有源汇，无下界，可行流，无费用。

　　……

　　5.有源汇，无下界，可行流，有费用。

　　可以证明，如果求最小费用，则费用随着流量的增加是增大的。最大费用则相反。所以只要费用的符号一变就立即停止增广。

　　6.有源汇，有下界，最大流，无费用。

　　先从t连向s，容量设为无穷大。这样就变成了无源汇的情况。将每条有下界的边先满上下界的流量，然后更新盈余量（入的流量-出的流量）。新建超级源ss和超级汇tt，若某个点u的盈余量>0则ss--->u，容量为u的盈余量。否则u--->tt，容量为u的盈余量的相反数。至于为什么，可以参见周源大牛的《一种简易的方法求解流量有上下界的网络中网络流问题》。这里我们只做简单解释。如果一个点的盈余量>0，则它是一定要流出去的，所以要从ss连向它，使它去找这些流量的出路。建完了图以后求一遍最大流，如果从ss连出的所有边都满流，则有解。在得到的残留网络（原图）上再求一次最大流即可。

　　7.有源汇，有下界，最大流，有费用。

　　=6 + 2

　　8.有源汇，有下界，最小流，无费用。

　　方法几乎同6，差别在于t先不连s，建新图-->最大流-->然后t-->s-->然后最大流。答案既是t-->s的流量。这么做是为了保证t-->s的流量最小，在有环流的情况可能不如此会出错。

　　9.有源汇，有下界，最小流，有费用。

　　做的时候先遍历最小的费用即可。

　　10.有源汇，有下界，可行流，无费用。

　　……

　　11.有源汇，有下界，可行流，有费用。

　　如6那样建图，在新图上先最大流，最小费用，然后在残留网络上（原图）做5.

　　12.无源汇，无下界，。。。。。。

　　不会……

　　13.无源汇，有下界，最大流。。。。。。

　　不会……

　　14.无源汇，有下界，可行流，。。。（同上）

 

　　15.有负权环的费用流

　　先将负边强制满流即可。满流方法在6中已提到过，不再详述。

转载于:https://www.cnblogs.com/lazycal/p/Net_Flow.html