朱全民專題網(wǎng)絡流算法

1、圖論算法 -最大流問題長沙市雅禮中學朱 全 民 運輸網(wǎng)絡現(xiàn)在想將一些物資從S運抵T，必須經(jīng)過一些中轉(zhuǎn)站。連接中轉(zhuǎn)站的是公路，每條公路都有最大運載量。 每條弧代表一條公路，弧上的數(shù)表示該公路的最大運載量。最多能將多少貨物從S運抵T？ 4248473 621STV1V2V3V4公路運輸圖基本概念這是一個典型的網(wǎng)絡流模型。為了解答此題，我們先了解網(wǎng)絡流的有關定義和概念。若有向圖G=(V,E)滿足下列條件： 有且僅有一個頂點S，它的入度為零，即d-(S) = 0，這個頂點S便稱為源點，或稱為發(fā)點。有且僅有一個頂點T，它的出度為零，即d+(T) = 0，這個頂點T便稱為匯點，或稱為收點。每一條弧都有非負

2、數(shù)，叫做該邊的容量。邊(vi, vj)的容量用cij表示。則稱之為網(wǎng)絡流圖，記為G = (V, E, C)可行流可行流對于網(wǎng)絡流圖G，每一條弧(i,j)都給定一個非負數(shù)fij，這一組數(shù)滿足下列三條件時稱為這網(wǎng)絡的可行流，用f表示它。1. 每一條弧(i,j)有fijCij2. 流量平衡除源點S和匯點T以外的所有的點vi，恒有： j(fij)= k(fjk)該等式說明中間點vi的流量守恒，輸入與輸出量相等。3.對于源點S和匯點T有 ，i(fSi)= j(fjT)= V(f)可改進路 給定一個可行流f=fij。若fij = Cij，稱為飽和?。环駝t稱為非飽和弧。若fij = 0，稱為零流??；否則稱為

3、非零流弧。定義一條道路P，起點是S、終點是T。把P上所有與P方向一致的弧定義為正向弧，正向弧的全體記為P+；把P上所有與P方向相悖的弧定義為反向弧，反向弧的全體記為P-。譬如在圖中，P = (S, V1, V2, V3, V4, T)，那么P+ = , , , P- = 給定一個可行流f，P是從S到T的一條道路，如果滿足：對于任意,fij是非飽和流，并且 P+ 或 fij是非零流，并且 P-那么就稱P是f的一條可改進路。（有些書上又稱：可增廣軌）之所以稱作“可改進”，是因為可改進路上弧的流量通過一定的規(guī)則修改，可以令整個流量放大。 割切 G = (V, E, C)是已知的網(wǎng)絡流圖，設U是V的一

4、個子集，W = VU，滿足SU，TW。即U、W把V分成兩個不相交的集合，且源點和匯點分屬不同的集合。對于弧尾在U，弧頭在W的弧所構(gòu)成的集合稱之為割切，用（U，W）表示。把割切（U，W）中所有弧的容量之和叫做此割切的容量，記為C（U，W），即：上例中，令U = S, V1，則W = V2, V3, V4, T，那么C(U, W) = + + + =8+4+4+1=17割切上例中，令U = S, V1，則W = V2, V3, V4, T，那么，C(U, W) = + + + =8+4+4+1=17流量算法的基本理論定理1：對于已知的網(wǎng)絡流圖，設任意一可行流為f，任意一割切為(U, W)，必有：V

5、(f) C(U, W)。/切割將網(wǎng)絡流圖分為兩部分,所以最大流不可能大于這兩部分的連接值即C(U,W)定理2：可行流f是最大流的充分必要條件是：f中不存在可改進路。定理3：整流定理。如果網(wǎng)絡中所有的弧的容量是整數(shù)，則存在整數(shù)值的最大流。定理4：最大流最小割定理。最大流等于最小割，即max V(f) = min C(U, W)。 最大流算法第1步，令x=(xij)是任意整數(shù)可行流，可能是零流，給s一個永久標號(-, )。第2步(找增廣軌)，如果所有標號都已經(jīng)被檢查，轉(zhuǎn)到第4步。 找到一個標號但未檢查的點i, 并做如下檢查，對每一個弧(i,j),如果xij0,且j未標號，則給j一個標號(-i, (

6、j) ),其中， (j)=minxji , (i) 第三步(增廣)，由點t開始，使用指示標號構(gòu)造一個增廣路,指示標號的正負則表示通過增加還是減少弧流量來增加還是減少弧流量來增大流量，抹去s點以外的所有標號，轉(zhuǎn)第二步繼續(xù)找增廣軌。第四步(構(gòu)造最小割)，這時現(xiàn)行流是最大的，若把所有標號的集合記為S，所有未標號點的集合記為T,便得到最小容量割(S,T)。實例復雜度分析設圖中弧數(shù)為m,每找一條增廣軌最多需要進行2m次弧的檢查。如果所有弧的容量為整數(shù)，則最多需要v(其中v為最大流)次增廣，因此總的計算量為O(mv)。procedure maxflow; 最大流var i, j, delta, x : i

7、nteger; last : tline; 可改進路中的前趨 check : array0 . maxn of boolean; 檢查數(shù)組begin repeat fillchar(last, sizeof(last), 0); fillchar(check, sizeof(check), false); last1 := maxint; repeat i := 0; repeat inc(i) until (i n) or (lasti 0) and not checki; 找到一個已檢查而未標號的點 if i n then break; for j := 1 to n do if last

8、j = 0 then if flowi, j 0 then lastj := -i; 反向弧 checki := true; until lastn 0; if lastn = 0 then break; delta := maxint; i := n; repeat j := i; i := abs(lastj); if lastj 0 then x := limiti, j - flowi, j else x := flowj, i; if x 0 then inc(flowi, j, delta) else dec(flowj, i, delta); until i = 1; 放大網(wǎng)絡流

9、 until false;end;費用流流最重要的應用是盡可能多的分流物資，這也就是我們已經(jīng)研究過的最大流問題。然而實際生活中，最大配置方案肯定不止一種，一旦有了選擇的余地，費用的因素就自然參與到?jīng)Q策中來。右圖是一個最簡單的例子：弧上標的兩個數(shù)字第一個是容量，第二個是費用。這里的費用是單位流量的花費，譬如fs1=4，所需花費為3*4=12。容易看出，此圖的最大流（流量是8）為：fs1 = f1t = 5, fs2 = f2t = 3。所以它的費用是：5*3+5*4+3*7+3*2 = 62。(6,3)(5,4)(3,7)(8,2)STV1V2費用流問題費用流定義設有帶費用的網(wǎng)絡流圖G = (V

10、, E, C, W)，每條弧對應兩個非負整數(shù)Cij、Wij，表示該弧的容量和費用。若流f滿足：流量V(f)最大。滿足a的前提下，流的費用Cost(f) =E (fij * Wij)最小。就稱f是網(wǎng)絡流圖G的最小費用最大流。最小費用可改進路設P是流f的可改進路，定義P+ Wij - P- Wij 為P的費用(為什么如此定義？)如果P是關于f的可改進路中費用最小的，就稱P是f的最小費用可改進路。 算法求最小費用最大流的基本思想是貪心法。即：對于流f，每次選擇最小費用可改進路進行改進，直到不存在可改進路為止。這樣的得到的最大流必然是費用最小的。算法可描述為：第1步. 令f為零流。第2步. 若無最小費

11、用可改進路，轉(zhuǎn)第5步；否則找到最小費用可改進路，設為P。第3步. 根據(jù)P求delta（改進量）。第4步. 放大f。轉(zhuǎn)第2步。第5步. 算法結(jié)束。此時的f即最小費用最大流。 如何求最小費用可改進路 設帶費用的網(wǎng)絡流圖G = (V, E, C, W)，它的一個可行流是f。我們構(gòu)造帶權有向圖B = (V, E)，其中：V = V。若E，fijCij，那么E，權為Wij。若E，fij0，那么E，權為-Wij。顯然，B中從S到T的每一條道路都對應關于f的一條可改進路；反之，關于f的每條可改進路也能對應B中從S到T的一條路徑。即兩者存在一一映射的邏輯關系。故若B中不存在從S到T的路徑，則f必然沒有可改進路

12、；不然，B中從S到T的最短路徑即為f的最小費用可改進路?，F(xiàn)在的問題變成：給定帶權有向圖B = (V, E)，求從S到T的一條最短路徑。迭代法求最短路經(jīng)考慮到圖中存在權值為負數(shù)的弧，不能采用Dijkstra算法；Floyd算法的效率又不盡如人意所以，這里采用一種折衷的算法：迭代法。設Shorti表示從S到i頂點的最短路徑長度；從S到頂點i的最短路徑中，頂點i的前趨記為Lasti。那么迭代算法描述如下：（為了便于描述，令n = |V|，S的編號為0，T的編號為n+1）step 1. 令Shorti +（1in+1），Short0 0。step 2. 遍歷每一條弧。若Shorti + Shortj，

13、則令Shortj Shorti + ，同時Lastj i。重復做step 2直到不存在任何任何弧滿足此條件為止。step 3. 算法結(jié)束。若Shortn + 1= +，則不存在從S到T的路徑；否則可以根據(jù)Last記錄的有關信息得到最短路徑。一次迭代算法的時間復雜度為O(kn2)，其中k是一個不大于n的變量。在費用流的求解過程中，k大部分情況下都遠小于n。procedure costflow; 求最小費用最大流var i, j, x, delta : integer; best, last : tline; best：最短路長度；last：可改進路中的前趨頂點 more : boolean;be

14、gin repeat fillword(best, sizeof(best) shr 1, maxint); fillchar(last, sizeof(last), 0); last1 := maxint; best1 := 0; 賦初值 repeat more := false; for i := 1 to n do if besti maxint then for j := 1 to n do begin if (flowi, j limiti, j) and (besti + costi, j 0) and (besti - costj, i 0 then x := limiti, j

15、 - flowi, j else x := flowj, i; if x 0 then inc(flowi, j, delta) else dec(flowj, i, delta); until i = 1; until false; 根據(jù)改進量放大流end; 思維發(fā)散與探索 可改進路費用：“遞增！遞增？”設f從零流到最大流共被改進了k次，每i次選擇的可改進路的費用為pi，那么會不會有p1p2p3pk呢？迭代法：“小心死循環(huán)！嘿嘿”迭代法會出現(xiàn)死循環(huán)嗎？也就是說，構(gòu)造的帶權有向圖B中會存在負回路嗎？費用：“你在乎我是負數(shù)嗎？”容量：“我管的可不僅是弧?！本W(wǎng)絡流圖中的“容量”都是對弧而言的，但若

16、是給每個頂點也加上一個容量限制：即通過此頂點的流量的上限；任務仍然是求從S到T的最小費用最大流。你能解決嗎？有上下界的最大流 上面討論的網(wǎng)絡流都只對每條弧都限定了上界（其實其下界可以看成0），現(xiàn)在給每條弧加上一個下界限制Aij (即必須滿足Aijfij)?；∩蠑?shù)字對第一個是上界，第二個是下界。若是撇開下界不看，此圖的最大流如圖所示，流量是6；但若是加入了下界的限制，它的最大流量就只有5了。 (3,0)(3,0)(3,0)(3,0)(10,1)原問題33330(a)32231(b)增廣怎樣找可行流一種自然的想法是去掉下界，將其轉(zhuǎn)化為只含上界的網(wǎng)絡流圖。這種美好的愿望是可以實現(xiàn)的。具體方法如下：設

17、原網(wǎng)絡流圖為G = (V, E, C, A)，構(gòu)造不含下界的網(wǎng)絡流圖G = (V, E, C)：V = VS, T對每個頂點x，令h-(x)= E AiX ，若h-(x)0，就添加一條弧，其上界為h-(x) 。對每個頂點x，令h+(x)= E AXi ，若h+(x)0，就添加一條弧，其上界為h+(x) 。對于任何E，都有E，其上界Cij = Cij Aij。新增E，其上界CTS = +。在G中以S為源點、T為匯點求得最大流f。若f中從S發(fā)出的任意一條弧是非飽和弧，則原網(wǎng)絡流圖沒有可行流。否則可得原圖的一個可行流f = f + A，即所有的fij = f ij + Aij 。然后再求可改進路（反

18、向弧必須滿足fijAij，而非fij0），不斷放大f，直到求出最大流。多源點、多匯點的最大流已知網(wǎng)絡流圖有n個源點S1、S2、Sn，m個匯點T1、T2、Tm，求該圖的最大流。這樣的問題稱為多源點、多匯點最大流。它的解決很簡單：增設一個“超級源”S，對每個源點Si，新增弧，容量為無窮大。增設一個“超級匯”T，對每個匯點Ti，新增弧，容量為無窮大。以S為源點、T為匯點求最大流f。將f中的S和T去掉，即為原圖的最大流。頂點有容量限制的最大流對除源點和匯點之外的每個頂點i拆分成兩個頂點i和i。新增一條弧，其容量為點i的流量限制。對于原圖中的弧，我們將其變換成。對變換后的圖求最大流即可。這里我們運用到了

19、化歸的思想：將未知的“點限制”問題轉(zhuǎn)化為已知的“邊限制”問題 網(wǎng)絡流與二部圖的匹配設二部圖為G = (X, Y, E)。增設點S，對于所有iX，新增弧，容量為1；增設點T，對于所有iY，新增一條弧，容量也為1。原圖中所有的弧予以保留，容量均為+。對新構(gòu)造出來的網(wǎng)絡流圖以S為源點、T為匯點求最大流：流量即為最大匹配數(shù)；若?。╥X，jY）的流量非零，它就是一條匹配邊。二部圖最大匹配問題解決。那么二部圖的最佳匹配問題又如何？仍然按照上述方法構(gòu)圖。同時令原圖中弧的費用保持不變；新增弧的費用置為0。然后以S為源點、T為匯點求最小費用最大流即可。最大流的費用即為原二部圖最佳匹配的費用。 餐巾問題(HNOI

20、2001XB)某軟件公司正在規(guī)劃一項n天的軟件開發(fā)計劃，根據(jù)開發(fā)計劃第i天需要ni個軟件開發(fā)人員，為了提高工作效率，公司給軟件人員提供了很多的服務，其中一項服務就是要為每個開發(fā)人員每天提供一塊消毒毛巾，這種毛巾使用一天后必須再做消毒處理后才能使用。消毒方式有兩種，A種方式的消毒時間需要a天時間，B中方式的消毒需要b天時間（ba），A種消毒方式的費用為每塊毛巾fA，B種消毒方式的費用為每塊毛巾fB，而買一塊新毛巾的費用為f（新毛巾是已消毒的，當天可以使用）；而且ffAfB。公司經(jīng)理正在規(guī)劃在這n天中，每天買多少塊新毛巾、每天送多少塊毛巾進行A種消毒和每天送多少塊毛巾進行B種消毒。當然，公司經(jīng)理希

21、望費用最低。你的任務就是：求出提供毛巾服務的最低總費用。輸入文件：第1行為n, a, b, f, fA, fB. 第2行為n1, n2, , nn（注：1f, fA, fB60, 1n1000）輸出文件：最少費用輸入輸出示例：input.txt output.txt4 1 2 3 2 1 388 2 1 6分析公司第i天需要ni 塊毛巾，可以把這ni 塊毛巾的來源列舉如下：新買的毛巾。第i a 1天之前通過A種方式消毒的毛巾。第i b 1天之前通過B種方式消毒的毛巾。我們構(gòu)造帶費用的網(wǎng)絡流圖G = (V, E, C)。V = S, V1, V2, , Vn, V1, V2, , Vn, T，其

22、中S是源點、T是匯點。E中包含如下幾類?。海?in），容量為ni，費用為0。表示第i天需要ni塊毛巾。（1in），容量為正無窮大，費用為f。該弧的流量表示第i天通過方式a得到的毛巾數(shù)量。（a+2in），容量為正無窮大，費用為fA。該弧的流量表示第i天通過方式b得到的毛巾數(shù)量。（b+2in），容量為正無窮大，費用為fB。該弧的流量表示第i天通過方式c得到的毛巾數(shù)量。（2in），容量為正無窮大，費用為0。由于題目中沒有說消毒完的毛巾要馬上使用，所以第3天就消毒好的毛巾可以暫且留著，到第7天、第8天再使用也可以。因此這里增設此弧。（1in），容量為ni，費用為0。然后對這個網(wǎng)絡流圖以S為源點、T為匯

23、點的求最小費用最大流即可。求得的最大流費用就是原問題的答案。 Agent問題 (ctsc2001)有n名雙重間諜潛伏在敵軍內(nèi)部，分別編號為1, 2, 3, , n。在給定的時間內(nèi)，任意兩人之間至多只進行一次點對點的雙人聯(lián)系。數(shù)據(jù)將給你一份表格，表格中將提供任意兩位間諜i和j之間進行聯(lián)系的安全程度，用一個0，1的實數(shù)Sij表示；以及他們聯(lián)系時，能夠互相傳遞的消息的最大數(shù)目，用一個正整數(shù)表示Mij。（如果在表格中沒有被提及，那么間諜i和j之間不進行直接聯(lián)系）。假消息從盟軍總部傳遞到每個間諜手里的渠道也不是絕對安全的，我們用0，1的實數(shù)ASj表示總部與間諜j之間進行聯(lián)系的安全程度，AMj則表示總部和

24、間諜j之間進行聯(lián)系時傳遞的消息的最大數(shù)目。對于不和總部直接聯(lián)系的間諜，他的AMj=0（而表格中給出的他的ASj是沒有意義的）。當然，假消息從間諜手中交到敵軍的情報部官員的辦公桌上的過程是絕對安全的，也就是說，間諜與敵軍情報部門之間要么不進行聯(lián)系，要么其聯(lián)系的安全程度是1（即完全可靠）?，F(xiàn)在我軍司令部想利用這些間諜將k條假消息發(fā)布到敵軍情報機關的負責人。消息先由總部一次性發(fā)給n名間諜中的一些人，再通過它們之間的情報網(wǎng)傳播，最終由這n名間諜中某些人將情報送到敵軍手中。對于一條消息，只有安全的通過了所有的中轉(zhuǎn)過程到達敵軍情報部，這個傳遞消息的過程才算安全的；因此根據(jù)乘法原理，它的安全程度P就是從總部

25、出發(fā)，經(jīng)多次傳遞直到到達敵軍那里，每一次傳遞該消息的安全程度的乘積。而對于整個計劃而言，只有當k條消息都安全的通過情報網(wǎng)到達敵軍手中，沒有一條引起懷疑時，才算是成功的。所以計劃的可靠程度是所有消息的安全程度的乘積。顯然，計劃的可靠性取決于這些消息在情報網(wǎng)中的傳遞方法。你的任務是：擬定一個方案，確定消息應該從哪些人手中傳遞到哪些人手中，使得最終計劃的可靠性最大。輸入文件：第一行包括兩個整數(shù)N和K，分別是間諜的總?cè)藬?shù)和計劃包含的消息總數(shù)。第二行包括2n個數(shù)，前n個數(shù)實數(shù)AS1, AS2, , ASn（范圍在0, 1以內(nèi)）；后n個數(shù)是整數(shù)AM1, AM2, , AMn。第三行包含了n個整數(shù)，其中第i

26、（i = 1, 2, , n）個整數(shù)如果為0表示間諜i與敵軍情報部不進行聯(lián)系，如果為1則表示間諜與敵軍情報部進行聯(lián)系。第四行開始，每行包括4個數(shù)，依次分別是：代表間諜編號的正整數(shù)i和j，間諜i和j聯(lián)系的安全性參數(shù)Sij（0, 1范圍內(nèi)的實數(shù)），以及i、j之間傳遞的最大消息數(shù)Mij（每以行的i均小于j）。最后一行包含兩個整數(shù)-1 1，表示輸入數(shù)據(jù)的結(jié)束。0 n 300, 0 k 300。輸出文件：輸出文件中只有一行。這一行中包含一個實數(shù)P，給出的是整個計劃的可靠程度P，保留5位有效數(shù)字（四舍五入）。如果情報根本不能將K條消息傳到敵軍手中，那么計劃的可靠性為0。（你可以假定，如果計劃存在，那么它的

27、可靠性大于1e-12）輸入輸出樣例Agent.in Agent.out6 13 0.000211840.9 0.7 0.8 0 0 0 2 6 8 0 0 00 0 0 1 0 11 4 0.5 22 3 0.9 52 5 0.8 22 6 0.8 73 5 0.8 25 6 0.8 4-1 -1 分析題目中的“總部”、“敵軍情報部”與“間諜”的地位是完全相等的，為了方便敘述可以將兩者亦看作是間諜：“總部”編號為0、“敵軍情報部”編號為n+1。那么S0i = ASi，M0i = AMi；若間諜i可以與敵軍司令部直接聯(lián)系Si,n+1=1, Mi,n+1=+，否則Si,n+1=0, Mi,n+1=

28、0。我們構(gòu)造帶費用的網(wǎng)絡流圖G = (V, E, M, S)。（M為容量，S位費用）第i個間諜抽象成頂點i，另外增加匯點T。所有頂點構(gòu)成的集合記為V。若Mij0，則存在弧和：其容量皆為Mij；費用Sji =Sij = ln(Sij)。增設弧，其容量為k，費用為0。然后以V0為源點、T為匯點求最大費用最大流。若流量小于k，則不存在可行方案 不然則最大可靠性為：證明設最大費用最大流的費用為Cost，那么：因為Cost達到最大，所以可靠性也達到最大。證畢。Plan問題 某軟件公司有n個可選的程序項目，其中第i個項目需要耗費資金ai元，開發(fā)成功后可獲收益bi元。當然，程序項目之間不是獨立的：開發(fā)第i個

29、項目前，必須先開發(fā)出一些其他的項目（正如開發(fā)Office前必須開發(fā)Windows）。這些項目就稱為第i個項目的“前趨項目”?，F(xiàn)在給出所有項目的ai、bi，以及前趨項目。你的任務是：幫助該公司從這n個程序項目中選擇若干個進行開發(fā)，使得總收益最大。輸入文件：輸入文件有n + 3行。第1行包含一個整數(shù)n（1n200）。第2行有n個正整數(shù)a1, a2, , an。第3行有n個正整數(shù)b1, b2, , bn。第i + 3行（1in）包含若干正整數(shù)：ri, k1, k2, , kri。第一個數(shù)ri表示第i個項目共有多少前趨項目；接下來有ri個正整數(shù)k1, k2, , kri，分別表示每個前趨項目的編號。輸出文件：輸出文件只有一個整數(shù)max，表示最大收益。分析令di = bi ai，A = i | di 0，B = i | di 0。則di就是第i個項目的純收益，A是所有可以獲得利潤的項目集合，B是所有會導致虧損的項目集合。構(gòu)造網(wǎng)絡流圖G = (V, E, C)。V中包含兩類頂點：源點S，匯點T。將第i