網(wǎng)絡(luò)流與匹配問題最大流,最》ppt課件.ppt

《網(wǎng)絡(luò)流與匹配問題最大流,最》ppt課件.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、網(wǎng)絡(luò)流與匹配問題——最大流，最小費用最大流，最大匹配，最佳匹配李子星概念與定義對于一個有向圖G0=(V,E)，若其中的每條邊有一個非負(fù)實數(shù)值cuv表示這條邊的容量（對于不在圖中的邊定義cuv=0），且圖中有一個源點s和一個匯點t，且s<>t，那么可以稱這個圖為網(wǎng)絡(luò)圖，記為G1=(V,E,c,s,t)。對于網(wǎng)絡(luò)圖G1=(V,E,c,s,t)，若對任意的u和v屬于V且u<>v，都有一個非負(fù)實數(shù)值fuv表示邊上的流量，且滿足條件：對任意的u和v屬于V，有fuv<=cuv

2、，fuv=-fvu對任意的u屬于V且u<>s且u<>t，有sum{fuv

3、v屬于V}=0那么可以稱f為圖G1的一個可行流。概念與定義對于網(wǎng)絡(luò)圖G1=(V,E,c,s,t)的一個它的可行流f，定義sum{fsv

4、v屬于V}為f的流量。若f的流量為0，那么稱f為一個零流。對于網(wǎng)絡(luò)圖G1=(V,E,c,s,t)，其流量最大的可行流可以稱為G1的最大流。對于網(wǎng)絡(luò)圖G1=(V,E,c,s,t)和它的一個可行流f，若G2=(V,E,c’,s,t)滿足：對任意的u和v屬于V都有c’uv=cuv-fuv那么稱G

5、2為G1對可行流f的殘量網(wǎng)絡(luò)。概念與定義對于網(wǎng)絡(luò)圖G1和可行流f的殘量網(wǎng)絡(luò)G2=(V,E,c’,s,t)上的任意一條s到t的路徑p=，uf(p)=min{c’vi-1vi

6、1<=i<=k}可以稱為這條路徑的可改進(jìn)量。對于網(wǎng)絡(luò)圖G1和流量f的殘量網(wǎng)絡(luò)G2上的任意一條s到t的路徑p，若uf(p)>0，那么稱p為G2上的一條增廣路。概念與定義由G2上的一條增廣路p=，可以得到G1的一個可行流f(p)：對任意的u和v屬于V且不屬于

7、p，f(p)uv=0對任意的0

8、殘量網(wǎng)絡(luò)G2若G2上存在s到t的增廣路p，則合并f和f(p)為新的f否則跳出循環(huán)最大流求G2上s到t的路徑p的方法可以隨便用，深搜廣搜都可以，肯定最多遍歷每條邊一次，因此找一次增廣路的時間復(fù)雜度為O(

9、E

10、)?？偟臅r間復(fù)雜度為O(D*

11、E

12、)，D為找增廣路的次數(shù)。最大流的Dinic算法計算殘量網(wǎng)絡(luò)忽略c為0的邊后的層次圖在殘量網(wǎng)絡(luò)中只保留i層指向i+1層的有向邊的情況下，找到所有存在的增廣路并合并至可行流中Dinic算法與層次圖i號節(jié)點的層次level[i]：從s點到i號節(jié)點最少要經(jīng)過的邊數(shù)，一

13、輪廣搜在O(

14、E

15、)的時間復(fù)雜度內(nèi)就能得到。源點Level=0Level=2Level=3Level=1Level=3Dinic算法的多路增廣得到殘量網(wǎng)絡(luò)的層次圖后，我們只考慮其中第i層指向i+1層的有向邊。funcFindPath(u,uf:int):intif(u=t)result:=ufelseuf’:=0;foreachvwhere(c[u,v]>0&&level[v]=level[u]+1&&uf’

16、]-=tuf;　c[v,u]+=tuf//合并流uf’+=tuf;if(uf’=0)level[u]:=-1;//u根本就沒有到t的路徑，以后也不用來了result:=uf’uf是當(dāng)前得到的s到u的路徑的可改進(jìn)量，返回值是從u到t的所有路徑的可改進(jìn)量的和與uf的較小值。uf‘是已經(jīng)找到的u到t的路徑的可改進(jìn)量的和。可行流的合并是這段代碼最難理解的地方。Dinic算法的多路增廣這個多路增廣的效率如何？每找到一條增廣路，至少會有一條邊被刪除，因此最多找

17、E

18、條增廣路。每條增廣路長度一定不超過

19、V

20、。

21、一輪多路增廣的時間復(fù)雜度就是O(

22、V

23、*

24、E

25、)Dinic算法的多路增廣經(jīng)過一輪多路增廣后，一定至少出現(xiàn)一個“斷層”，即存在某一層，這一層沒有指向下一層的邊。那么重新求得的層次圖的層數(shù)一定會增加，而層數(shù)最多就

26、V

27、層。所以Dinic算法的總的時間復(fù)雜度為O(

28、V

29、2

30、E

31、)，但實際運行效果非常好，對于節(jié)點數(shù)萬個，邊數(shù)達(dá)十萬條級別的圖，都能很快的出解。是傳說中效率最高的最大流算法。NOI2006最大獲利題意：有n個可能的中轉(zhuǎn)站，建造它需要花費P[i]，有m個用戶群，當(dāng)A[i]和B[i]兩個中轉(zhuǎn)站都