个人网络流知识小结
http://mindlee.net/2011/11/19/network-flow/ 好啊，入门资料，包括简单介绍网络流的知识概念以及Dinic的算法介绍，主要思想就是bfs进行分层，在dfs找增广路径，以及ISAP算法介绍，很全了
HDU3549 最简单的网络流入门题，poj1273 先是写了最基础的 Edmonds-karp(EK) 算法，时间复杂度为O(VE2) 有邻接矩阵的实现，还有邻接边的实现，后者容易出错！ 编程复杂度加大，不过效率较矩阵高。。可以用这个题目，用各个算法实现下，比较下时间运行情况
对于EK算法与ISAP算法的区别：
EK算法每次都要重新寻找增广路，寻找过程只受残余网络的影响，如果改变残余网络，则增广路的寻找也会随之改变；SAP算法预处理出了增广路的寻找大致路径，若中途改变残余网络，则此算法将重新进行。EK处理在运算过程中需要不断加边的最大流比SAP更有优势
3.Dinic算法 O(v2E) 代码分别有递归的实现，和非递归的实现版本 算法思想主要如下：
1.初始化流量，计算出剩余图
2.根据剩余图，计算层次图，如果汇点不在层次图中，那么算法结束
3.在层次图内不断用bfs增广，直到层次图内没有增广路为止
转2
4.ISAP算法，别人写的很好，理解了，直接摘抄了，引用http://www.zlinkin.com/?p=34
众所周知，在网络流的世界里，存在2类截然不同的求解思想，就是比较著名的预流推进与增广路，两者都需要反向边的小技巧。
其中预流推进的算法思想是以边为单元进行推流操作。具体流程如下:置初始点邻接边满流并用一次反向bfs对每个结点计算反向距离标号，定义除汇点外存量大于出量的结点为活动结点，每次对活动结点按允许边（u->v:d[u]=d[v]+1）进行推流操作，直到无法推流或者该点存量为0，若u点此时仍为活动结点，则进行重标号，使之等于原图中进行推操作后的邻接结点的最小标号+1，并将u点入队。当队列为空时，算法结束，只有s点和t点存量非0，网络中各顶点无存量，无法找到增广路继续增广，则t点存量为最大流。
而增广路的思想在于每次从源点搜索出一条前往汇点的增广路，并改变路上的边权，直到无法再进行增广，此时汇点的增广量即为最大流。两者最后的理论基础依然是增广路定理，而在理论复杂度上预流推进要显得比较优秀。其中的HLPP高标预流推进的理论复杂度已经达到了另人发指的O（sqrt(m)*n*n），但是其编程复杂度也是同样的令人发指- -
于是我们能否在编程复杂度和算法复杂度上找到一个平衡呢，答案是肯定的。我们使用增广路的思想，而且必须进行优化。因为原始的增广路算法（例如EK）是非常悲剧的。于是有人注意到了预流推进中的标号法，在增广路算法中引入允许弧概念，每次反搜残留网络得到结点标号，在正向增广中利用递归进行连续增广，于是产生了基于分层图的Dinic算法。一些人更不满足于常规Dinic所带来的提升，进而加入了多路分流增广的概念，即对同一顶点的流量，分多路同时推进，再加上比较复杂的手工递归，使得Dinic已经满足大部分题目的需要。
然而这样做就是增广路算法优化的极限么？答案永远是不。人们在Dinic中只类比了预流推进的标号技术，而重标号操作却没有发挥得淋漓尽致。于是人们在Dinic的基础上重新引入了重标号的概念，使得算法无须在每次增广后再进行BFS每个顶点进行距离标号，这种主动标号技术使得修正后算法的速度有了不少提高。但这点提高是不足称道的，人们又发现当某个标号的值没有对应的顶点后，即增广路被截断了，于是算法便可以提前结束，这种启发式的优化称为Gap优化。最后人们结合了连续增广，分层图，多路增广，Gap优化，主动标号等穷凶极恶的优化，更甚者在此之上狂搞个手动递归，于是产生了增广路算法的高效算法–ISAP算法。
虽然ISAP算法的理论复杂度仍然不可超越高标预流推进，但其编程复杂度已经简化到发指，如此优化，加上不逊于Dinic的速率（在效率上手工Dinic有时甚至不如递归ISAP），我们没有不选择它的理由。
5.自己的理解
不管怎样，普通的EK一般来说 复杂度是在O(n*m*m)的，而Dinic和ISAP都是O(n*n*m)d的，而ISAP的几个优化，有将效率进一步提升，关于复杂度的分析，算法导论有介绍，主要是理解下后面的分层思想和预留推进思想，以及根据dfs回朔来判断是否可以推进流还是做重标记等，这里可以用ISAP算法和DInic算法，其中主要难点是在网络流的建模上！
邻接表的建立也有许多巧妙之处，仅仅是数据结构上的邻接表，效率和空间浪费的简直令人发指！
接下来就是深入的部分，可以看得资料和论文如下：
http://acm.uestc.edu.cn/bbs/simple/?t704.html 很好，很全面的学习资料和总结题集
《Network Flows - Theory, Algorithms, And Applications》
《Combinatorial optimization:networks and matroids》
解决网络流的几种方案在这里，非常清楚
http://dantvt.is-programmer.com/tag/Dinic
自己上传的一点资料:
/Files/panzhizhou/国家集训队论文网络流整理.zip