最大流算法及其應(yīng)用

1、最大流算法及其應(yīng)用最大流算法及其應(yīng)用提要l網(wǎng)絡(luò)流相關(guān)的一些概念l最大流和最小割問題l最大流算法的應(yīng)用l總結(jié)一、網(wǎng)絡(luò)流相關(guān)的一些概念流網(wǎng)絡(luò) (Flow Network)l流網(wǎng)絡(luò)是一個有向圖G=(V,E)，其中每條邊(u,v)E均有一非負(fù)容量c(u,v)0。如果(u,v)E，則假定c(u,v)=0。流網(wǎng)絡(luò)中有兩個特別的頂點：源點源點s和匯點匯點t。圖1 一個流網(wǎng)絡(luò)的例子stv1v4v5v2v3v635221642314流 (Flow) lG的流是一個實值函數(shù)f，f(u,v)表示頂點u到頂點v的流，它可以為正，為零，也可以為負(fù)，且滿足下列三個性質(zhì)：l容量限制容量限制：對所有u,vV，要求f(u,v)

2、c(u,v)。l反對稱性反對稱性：對所有u,vV ，要求f(u,v)=-f(v,u)。l流守恒性流守恒性：對所有u,vV-s,t，要求( , )0v Vf u v流量l整個流網(wǎng)絡(luò)G的流量：( , )v Vff s v( , )u Vff u t割 (Cut) l流網(wǎng)絡(luò)G=(V,E)的割(S,T)將劃分成S和T=V-S兩部分，使得sS，tT。定義割(S,T)的容量為c(S,T)，則：,( , )( , )u S v Tc S Tc u v殘留網(wǎng)絡(luò) (Residual Network) l給定一個流網(wǎng)絡(luò)G=(V,E)和流f，由f壓得的G的殘留網(wǎng)絡(luò)Gf=(V,Ef)，定義cf(u,v)為殘留網(wǎng)絡(luò)Gf

3、中邊(u,v)的容量。如果弧(u,v)E或弧(v,u)E，則(u,v)Ef，且cf(u,v) =c(u,v)-f(u,v)。在下面的各種概念和方法中，我們只考慮殘留網(wǎng)絡(luò)中容量大于0的弧，但是編程時為了方便還是保留了。增廣路徑 (Augmenting Path)l對于殘留網(wǎng)絡(luò)Gf中的一條s-t路徑p稱其為增廣路徑，定義增廣路徑p的殘留容量為p上弧容量的最小值。后面求最大流要用到增廣路徑這個概念。增廣 (Augment)l對于殘留網(wǎng)絡(luò)Gf中的一條增廣路徑p，增廣的意思就是對于每一條屬于p的弧(u,v)，將f(u,v)增加p的殘留容量，將f(v,u)減少p的殘留容量。這樣的話，新的流f仍然滿足流的三

4、條性質(zhì)，并且原流網(wǎng)絡(luò)的流量|f|增加了。一般來說，增廣過后就會修改殘留網(wǎng)絡(luò)，易得對于每一條屬于p的弧(u,v)，要將cf(u,v)減去p的殘留容量， cf(v,u)加上p的殘留容量。（程序?qū)崿F(xiàn)基本都是通過直接修改殘留網(wǎng)絡(luò)來實現(xiàn)增廣的）二、最大流和最小割問題 最大流問題l對于一個流網(wǎng)絡(luò)G=(V,E)，其流量|f|的最大值稱為最大流，最大流問題就是求一個流網(wǎng)絡(luò)的最大流。增廣路定理l 當(dāng)且僅當(dāng)由當(dāng)前的流f壓得的殘留網(wǎng)絡(luò)Gf中不存在增廣路徑時，流f的流量|f|達到最大。（證明在此略去，可以參見相關(guān)書籍）l 根據(jù)增廣路定理，我們可以設(shè)計出最基本的求最大流的方法，一開始將流網(wǎng)絡(luò)G=(V,E)的流f置為零流

5、，即對于(u,v)E時，f(u,v)=0。然后構(gòu)建殘留網(wǎng)絡(luò)，尋找增廣路徑增廣，再修改殘留網(wǎng)絡(luò)，重復(fù)此過程，直到無法找到增廣路徑。此方法（之所以不是算法，是因為實現(xiàn)方法很多）稱為Ford-Fulkerson方法。Ford-Fulkerson方法的偽代碼lFORD-FULKERSON-METHORD (G, s, t)l1 initialize flow f to 0l2 while there exists an augmenting path pl3 do augment flow f along pl4 return f 最小割問題l最小割是指流網(wǎng)絡(luò)中容量最小的割。lFord-Fulkers

6、on定理（最小割最大流定定理（最小割最大流定理）：理）：在流網(wǎng)絡(luò)中，最小割的容量等于最大流的流量。（證明也在此略去）l根據(jù)這個定理，我們就可以通過求流網(wǎng)絡(luò)的最大流來得到最小割。最大流算法l前面所講的只是求最大流的一種方法，但怎樣高效地實現(xiàn)還是一個問題。l這個方法的最大問題就在于怎樣快速地找到一條增廣路徑。當(dāng)然我們可以用最基本的搜索（DFS或BFS），但是這種方法肯定不夠高效，這時我們就需要更高效的算法。l本文將重點介紹一種高效且實用的最大流算法：SAP算法算法（最短增廣路算法）。最短增廣路算法l即每次尋找包含弧的個數(shù)最少的增廣路進行增廣，可以證明，此算法最多只需要進行mn/2次增廣。并且引入距

7、離標(biāo)號的概念，可以在O(n)的時間里找到一條最短增廣路。最終的時間復(fù)雜度為O(n2m)，但在實踐中，時間復(fù)雜度遠遠小于理論值（特別是加了優(yōu)化之后），因此還是很實用的。（此段中n表示頂點數(shù)|V|，m表示邊數(shù)|E|）距離標(biāo)號l對于每個頂點i賦予一個非負(fù)整數(shù)值d(i)來描述i到t的“距離”遠近，稱它為距離標(biāo)號，并且滿足以下兩個條件：ld(t)=0l對于殘留網(wǎng)絡(luò)Gf中的一條弧(i,j)，d(i)d(j)+1。 允許弧和允許路l如果殘留網(wǎng)絡(luò)Gf中的一條弧(i,j)滿足d(i)=d(j)+1，我們稱(i,j)是允許弧，由允許弧組成的一條s-t路徑是允許路。顯然，允許路是殘留網(wǎng)絡(luò)Gf中的一條最短增廣路。當(dāng)找

8、不到允許路的時候，我們需要修改某些點的d(i)。算法基本架構(gòu)l Procedure Shortest_Augmenting_Path;l Varl l Beginl 預(yù)處理流為零流，建立殘留網(wǎng)絡(luò)l 計算距離函數(shù)d(i)l /實際上一開始沒有必要用BFS計算，清零就行了l i:=s;l while d(s)n dol beginl if i出發(fā)有允許弧(i,j) thenl beginl 記錄j在允許路上的前驅(qū)結(jié)點il i:=j;l if i=t thenl beginl 沿著增廣路增廣，修改殘留網(wǎng)絡(luò)l i:=s;l end;l endl elsel if i出發(fā)有弧 thenl d(i)=mi

9、n d(j)+1 | (i,j)在殘留網(wǎng)絡(luò)中l(wèi) elsel beginl d(i):=n; /禁止以后再考慮頂點il 當(dāng)is時退回到前一步l end;l end;l End;SAP的優(yōu)化lSAP算法有兩個重要的優(yōu)化：Gap優(yōu)化優(yōu)化和當(dāng)前弧優(yōu)化當(dāng)前弧優(yōu)化。Gap優(yōu)化l 我們可以注意到由于殘留網(wǎng)絡(luò)的修改只會使d(i)越來越大（因為修改前d(i)d(j)+1，而修改后會存在d(i)=d(j)+1，因此變大了），所以說d(i)是單調(diào)遞增的，這就提示我們，如果d函數(shù)出現(xiàn)了“斷層”，即沒有d(i)=k，而有d(i)=1，這時候必定無法再找到增廣路徑。我們可以這么想，現(xiàn)在的i滿足d(i)=k+1，發(fā)現(xiàn)沒有一

10、個d(j)為k，因此就會嘗試去調(diào)整d(i)，但是d(i)是單調(diào)遞增的，只會越來越大，所以k這個空缺便永遠不會被補上，也就是說無法再找到增廣路徑。當(dāng)前弧優(yōu)化l可以注意到一個事實：如果說在某次迭代中從i出發(fā)的弧(i,j)不是允許弧，則在頂點i的標(biāo)號修改之前(i,j)都不可能是允許弧。（因為d(i)不變，d(j)不減且d(i)d(j)+1）這樣，在查找允許弧的時候只需要從上一次找到的允許弧開始找。所以我們增加“當(dāng)前弧”這個數(shù)據(jù)結(jié)構(gòu)，記錄當(dāng)前頂點找到的允許弧，只有在修改這個頂點標(biāo)號時才會更改這個頂點的當(dāng)前弧。SAP的兩個優(yōu)化效果比較l（程序1：SAP 程序2：SAP+Gap 程序3：SAP+當(dāng)前弧 程

11、序4：SAP+Gap+當(dāng)前弧）l測試題目：NOI2006最大獲利比較結(jié)果（表中時間單位：s）測試點測試點1 1測試點測試點2 2測試點測試點3 3測試點測試點4 4測試點測試點5 5測試點測試點6 6測試點測試點7 7測試點測試點8 8測試點測試點9 9程序程序1 10.010.040.060.040.060.060.10TLETLE程序程序2 20.020.020.020.020.010.010.021.621.64程序程序3 30.020.020.030.030.040.030.05TLETLE程序程序4 40.010.010.020.020.020.020.010.150.15（測試環(huán)境

12、：Core 2 Duo E4600 2.4 GHz / 2GB）論效果的話，可能Gap優(yōu)化占了上風(fēng)，但是想要獲得最佳效果，還是要把兩種優(yōu)化結(jié)合起來使用的。三、最大流算法的應(yīng)用最大流模型l一個典型的最大流模型就是二分圖的最大二分匹配。l二分圖G=(X,Y,E)，其中X和Y是兩個不相交的點集，并且對于每對(u,v)E，uX且vY。二分圖的最大二分匹配問題就是從E中選擇一些邊，使得每個點最多在選擇的邊里出現(xiàn)一次，問最多能選多少條邊。圖2 一個二分圖的例子及其最大匹配（實線表示選中的邊，虛線表示未選中的邊）分析l實際上我們可以將二分圖的最大匹配問題轉(zhuǎn)換為最大流問題。增加源和匯，將源連到每個左邊的點，將

13、每個右邊的點連到匯，并把原來的邊改為有向的，從左邊的點指向右邊的點，最后把圖中所有弧的容量賦為1，這個流網(wǎng)絡(luò)的最大流即為原二分圖的最大匹配。圖3 新建的流網(wǎng)絡(luò)（圖中弧的容量均為1）st分析（續(xù)）l對于每個左邊的點，進去的流量最多只有1；對于每個右邊的點，出去的流量最多只有1，所以每個點最多在選中的邊里最多出現(xiàn)一次（選中的邊即為中間流量為1的?。?。又因為流最大，所以結(jié)果就是原二分圖的最大二分匹配。l關(guān)于二分圖的最大二分匹配還有另外一種算法：匈牙利算法，具體的內(nèi)容可以參閱其他資料。最小割模型l最小割問題是網(wǎng)絡(luò)流建模里的一個難點，由于最小割模型在原問題中往往很隱蔽，有時確實需要憑感覺。l看一道比較有

14、難度的例題最大獲利（NOI2006第二試）：最大獲利l 【問題描述】l 新的技術(shù)正沖擊著手機通訊市場，對于各大運營商來說，這既是機遇，更是挑戰(zhàn)。THU集團旗下的CS&T通訊公司在新一代通訊技術(shù)血戰(zhàn)的前夜，需要做太多的準(zhǔn)備工作，僅就站址選擇一項，就需要完成前期市場研究、站址勘測、最優(yōu)化等項目。l 在前期市場調(diào)查和站址勘測之后，公司得到了一共N個可以作為通訊信號中轉(zhuǎn)站的地址，而由于這些地址的地理位置差異，在不同的地方建造通訊中轉(zhuǎn)站需要投入的成本也是不一樣的，所幸在前期調(diào)查之后這些都是已知數(shù)據(jù)：建立第i個通訊中轉(zhuǎn)站需要的成本為Pi（1iN）。l 另外公司調(diào)查得出了所有期望中的用戶群，一共M個

15、。關(guān)于第i個用戶群的信息概括為Ai, Bi和Ci：這些用戶會使用中轉(zhuǎn)站Ai和中轉(zhuǎn)站Bi進行通訊，公司可以獲益Ci。（1iM, 1Ai, BiN）l THU集團的CS&T公司可以有選擇的建立一些中轉(zhuǎn)站（投入成本），為一些用戶提供服務(wù)并獲得收益（獲益之和）。那么如何選擇最終建立的中轉(zhuǎn)站才能讓公司的凈獲利最大呢？（凈獲利 = 獲益之和 - 投入成本之和）l 【輸入格式】l 輸入文件中第一行有兩個正整數(shù)N和M 。l 第二行中有N個整數(shù)描述每一個通訊中轉(zhuǎn)站的建立成本，依次為P1, P2, , PN 。l 以下M行，第(i + 2)行的三個數(shù)Ai, Bi和Ci描述第i個用戶群的信息。l 所有變量的

16、含義可以參見題目描述。l 【輸出格式】l 你的程序只要向輸出文件輸出一個整數(shù)，表示公司可以得到的最大凈獲利。l 【輸入樣例】l 5 5l 1 2 3 4 5l 1 2 3l 2 3 4l 1 3 3l 1 4 2l 4 5 3l 【輸出樣例】l 4l 【樣例說明】l 選擇建立1、2、3號中轉(zhuǎn)站，則需要投入成本6，獲利為10，因此得到最大收益4。l 【評分方法】l 本題沒有部分分，你的程序的輸出只有和我們的答案完全一致才能獲得滿分，否則不得分。l 【數(shù)據(jù)規(guī)模和約定】l 80%的數(shù)據(jù)中：N200，M1 000。l 100%的數(shù)據(jù)中：N5 000，M50 000，0Ci100，0Pi100。分析l看

17、到了“最大”這個字眼，很多人便以為此題與最小割沒有關(guān)系，但實際上不是。由于：l凈獲利 = 獲益之和 - 投入成本之和l = 所有用戶群的獲益 - （損失用戶群的獲益 + 建設(shè)中轉(zhuǎn)站的代價）l要使凈獲利最大，即使（損失用戶群的獲益 + 建設(shè)中轉(zhuǎn)站的代價）最小，這就將“最大”變成了“最小”。建模l 下面建立流網(wǎng)絡(luò)，以每一個中轉(zhuǎn)站和用戶群為頂點，并增加源和匯。連接源到每個中轉(zhuǎn)站，容量為建設(shè)該中轉(zhuǎn)站的代價；連接每個用戶群到匯，容量為該用戶群的收益；對于每個用戶群，連接它的兩個相關(guān)中轉(zhuǎn)站到這個用戶群，容量為。由于割將所有的點分為S和T兩個集合，又因為是最小割，所以割的容量必定不會包含中間那些容量為的弧，因此每個用戶群及其兩個相關(guān)的中轉(zhuǎn)站必定在一個集合中。那么T中包含的中轉(zhuǎn)站便是我們選擇建設(shè)的，S中包含的用戶群即為放棄的用戶群。割的容量為源到所有T中包含的中轉(zhuǎn)站的建設(shè)費用和加上S中包含的所有用戶的獲益和。又因為割