個人網絡流知識小結
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