Max Flow-SAP-Improved Shortest Augmenting [转]

322e

　　Ford-Fulkerson, Dinic, ISAP, EK等都是SAP
　　都是基於找出一個最短路徑再進行增廣的演算法
　　
　　但一般俗稱的SAP應該是ISAP (Improved Shortest Augmenting Paths)
　　他不用一個像EK一樣一直用BFS找一個最短路徑再進行增廣
　　而是只求一次最短路徑，接著都維護距離值，而不是重新搜索路徑
　　因此可將BFS O(E)的時間降低為O(V)因此EK的O(VE^2)可降為O(V^2E)
　　時間複雜度變得與Dinic一樣
　　
　　演算法步驟為
　　1.由sink做BFS找個點到sink的最短距離 (其實此步可不做，但要將距離初始為零)
　　2.由source作為當前點，找出一個點使的這個點到sink的距離比當前點到sink的距離少1
　　3.若存在這樣的點，就將此點作為當前點繼續搜索
　　若此點為sink，則沿著增廣路徑找尋最大流並修改residual graph
　　若不存在這樣的點，則修改距離值，找當前點所連到的點，且連過去的邊需存在流量，找出其中的到sink距離最短的點
　　並將當前的距離值更新為那一點的距離值+1，並將當前點設為之前增廣路徑連至目前當前點的點
　　4.直到source已不存在路徑到達sink時結束
　　
　　實際側了UVa的10330，運行時間與Dinic相同，效果相當不錯，可惜無法進榜
　　可見我的最大流還是不夠快....
　　
　　[转] http://kuoe0.pixnet.net/blog/post/18790432-%5Balgorithm%5Dmax-flow---sap---improved-shortest-augmenting-pat