网络流主要包括：

1、最大流

2、费用流

3、有上下界的网络流

网络流的基本技巧：

1、多个源点和汇点的情况。建立超级源点和超级汇点。

2、顶点有容量限制。拆成两个点，此两点连边，容量为原来的点被限制的容量。

3、最大费用转为最小费用。变负数，最后变回来。

一、最大流

最大流算法的思想是不断地找S到T的增广路。算法的效率是由找增广路的方法决定的。

Edmond - Karp算法：用广搜找增广路，时间复杂度 O (n*m*m )。思路最简单。

SAP算法：在寻找增广路的时候用了允许弧，并且用了Dinic算法的优化。时间复杂度为O(m*n*n)。

Dinic算法：时间复杂度为O(m*n*n)。

个人体会：最大流的题目一般不要求对算法进行修改（模版），难点在于如何把问题转为最大流问题，建图是一个难点。巧妙的建图可以把点的数量减少，从而减少时间复杂度。有一个文档叫网络流建模汇总，做得非常好。

题目链接http://www.cnblogs.com/Potato-lover/category/611621.html

1、判断满流

3572  Task Schedule 

2883  kebab

2、二分+最大流

传送门：

3、最短路+最大流

3416 Marriage Match IV

二、费用流

一般情况下都是求最大流条件下的最小费用。

算法： 连续最短路算法。

时间复杂度O（C*k*m），C是最终的流量，k*m就是SPFA算法的时间复杂度。

题目链接：http://www.cnblogs.com/Potato-lover/category/615756.html

三、有上下界的网络流

已经做过总结：http://www.cnblogs.com/Potato-lover/p/4002823.html

网络流小结