《網(wǎng)絡(luò)流算法專(zhuān)題》PPT課件

圖論算法-最大流問(wèn)題,長(zhǎng)沙市雅禮中學(xué)朱全民,運(yùn)輸網(wǎng)絡(luò),現(xiàn)在想將一些物資從S運(yùn)抵T，必須經(jīng)過(guò)一些中轉(zhuǎn)站。連接中轉(zhuǎn)站的是公路，每條公路都有最大運(yùn)載量。每條弧代表一條公路，弧上的數(shù)表示該公路的最大運(yùn)載量。最多能將多少貨物從S運(yùn)抵T？,基本概念,這是一個(gè)典型的網(wǎng)絡(luò)流模型。為了解答此題，我們先了解網(wǎng)絡(luò)流的有關(guān)定義和概念。若有向圖G=(V,E)滿足下列條件：有且僅有一個(gè)頂點(diǎn)S，它的入度為零，即d-(S)=0，這個(gè)頂點(diǎn)S便稱(chēng)為源點(diǎn)，或稱(chēng)為發(fā)點(diǎn)。有且僅有一個(gè)頂點(diǎn)T，它的出度為零，即d+(T)=0，這個(gè)頂點(diǎn)T便稱(chēng)為匯點(diǎn)，或稱(chēng)為收點(diǎn)。每一條弧都有非負(fù)數(shù)，叫做該邊的容量。邊(vi,vj)的容量用cij表示。則稱(chēng)之為網(wǎng)絡(luò)流圖，記為G=(V,E,C),可行流,可行流對(duì)于網(wǎng)絡(luò)流圖G，每一條弧(i,j)都給定一個(gè)非負(fù)數(shù)fij，這一組數(shù)滿足下列三條件時(shí)稱(chēng)為這網(wǎng)絡(luò)的可行流，用f表示它。1.每一條弧(i,j)有fijCij2.流量平衡除源點(diǎn)S和匯點(diǎn)T以外的所有的點(diǎn)vi，恒有：j(fij)=k(fjk)該等式說(shuō)明中間點(diǎn)vi的流量守恒，輸入與輸出量相等。3.對(duì)于源點(diǎn)S和匯點(diǎn)T有，i(fSi)=j(fjT)=V(f),可增廣路,給定一個(gè)可行流f=fij。若fij=Cij，稱(chēng)為飽和??；否則稱(chēng)為非飽和弧。若fij=0，稱(chēng)為零流?。环駝t稱(chēng)為非零流弧。定義一條道路P，起點(diǎn)是S、終點(diǎn)是T。把P上所有與P方向一致的弧定義為正向弧，正向弧的全體記為P+；把P上所有與P方向相悖的弧定義為反向弧，反向弧的全體記為P-。譬如在圖中，P=(S,V1,V2,V3,V4,T)，那么P+=,P-=給定一個(gè)可行流f，P是從S到T的一條道路，如果滿足：fij是非飽和流，并且P+,fij是非零流，并且P-那么就稱(chēng)P是f的一條可增廣路。之所以稱(chēng)作“可增廣”，是因?yàn)榭筛倪M(jìn)路上弧的流量通過(guò)一定的規(guī)則修改，可以令整個(gè)流量放大。,剩余圖(殘余網(wǎng)絡(luò)),剩余圖G=(V,E)流量網(wǎng)絡(luò)G=(V,E)中，對(duì)于任意一條邊(a,b)，若flow(a,b)0則(a,b)E,可以沿著a-b方向增廣,剩余圖中，從源點(diǎn)到匯點(diǎn)的每一條路徑都對(duì)應(yīng)一條增廣路,剩余圖中，每條邊都可以沿其方向增廣,剩余圖的權(quán)值代表能沿邊增廣的大小,G=(V,E,C)是已知的網(wǎng)絡(luò)流圖，設(shè)U是V的一個(gè)子集，W=VU，滿足SU，TW。即U、W把V分成兩個(gè)不相交的集合，且源點(diǎn)和匯點(diǎn)分屬不同的集合。對(duì)于弧尾在U，弧頭在W的弧所構(gòu)成的集合稱(chēng)之為割切，用（U，W）表示。把割切（U，W）中所有弧的容量之和叫做此割切的容量，記為C（U，W），即：,割切,割切示例,上例中，令U=S,V1，則W=V2,V3,V4,T，那么，C(U,W)=+=8+4+4+1=17,流量算法的基本理論,定理1：對(duì)于已知的網(wǎng)絡(luò)流圖，設(shè)任意一可行流為f，任意一割切為(U,W)，必有：V(f)C(U,W)。定理2：可行流f是最大流的充分必要條件是：f中不存在可改進(jìn)路。定理3：整流定理。如果網(wǎng)絡(luò)中所有的弧的容量是整數(shù)，則存在整數(shù)值的最大流。定理4：最大流最小割定理。最大流等于最小割，即maxV(f)=minC(U,W)。,最大流算法,第1步，令x=(xij)是任意整數(shù)可行流，可能是零流，給s一個(gè)永久標(biāo)號(hào)(-,)。第2步(找增廣路)，如果所有標(biāo)號(hào)都已經(jīng)被檢查，轉(zhuǎn)到第4步。找到一個(gè)標(biāo)號(hào)但未檢查的點(diǎn)i,并做如下檢查，對(duì)每一個(gè)弧(i,j),如果xij0,且j未標(biāo)號(hào)，則給j一個(gè)標(biāo)號(hào)(-i,(j),其中，(j)=minxji,(i)第3步(增廣)，由點(diǎn)t開(kāi)始，使用指示標(biāo)號(hào)構(gòu)造一個(gè)增廣路,指示標(biāo)號(hào)的正負(fù)則表示通過(guò)增加還是減少弧流量來(lái)增加還是減少弧流量來(lái)增大流量，抹去s點(diǎn)以外的所有標(biāo)號(hào)，轉(zhuǎn)第二步繼續(xù)找增廣軌。第4步(構(gòu)造最小割)，這時(shí)現(xiàn)行流是最大的，若把所有標(biāo)號(hào)的集合記為S，所有未標(biāo)號(hào)點(diǎn)的集合記為T(mén),便得到最小割(S,T)。,實(shí)例,復(fù)雜度分析,設(shè)圖中弧數(shù)為m,每找一條增廣軌最多需要進(jìn)行2m次弧的檢查。如果所有弧的容量為整數(shù)，則最多需要v(其中v為最大流)次增廣，因此總的計(jì)算量為O(mv)。,利用找增廣路的其他流量算法,增廣路的思想在于每次從源點(diǎn)搜索出一條前往匯點(diǎn)的增廣路，并改變路上的邊權(quán)，直到無(wú)法再進(jìn)行增廣：一般增廣路方法：在剩余圖中，每次任意找一條增廣路徑增廣。O(nmU)容量縮放增廣路方法:在剩余圖中，每次任意找一條最大可增廣容量和的增廣路徑增廣。O(nm*logU)最短增廣路方法(MPLA)：在剩余圖中，每次任意找一條含結(jié)點(diǎn)數(shù)最少的增廣路徑增廣。O(nm2)連續(xù)最短增廣路方法（DINIC）：在剩余圖中，每次BFS找增廣路徑增廣路徑時(shí)，記錄每個(gè)點(diǎn)的距離標(biāo)號(hào)。在距離標(biāo)號(hào)最短路圖上，不斷dfs找增廣路，即一次標(biāo)號(hào)，多次增廣。O(n2m),DINIC算法演示：,用預(yù)流推進(jìn)辦法求網(wǎng)絡(luò)流,預(yù)流推進(jìn)算法給每一個(gè)頂點(diǎn)一個(gè)標(biāo)號(hào)h(v)，表示該點(diǎn)到t的最短路（在殘量網(wǎng)絡(luò)中）。第一步hights()過(guò)程，就是BFS出初始最短路，計(jì)算出每一個(gè)頂點(diǎn)的h(v)。預(yù)流推進(jìn)算法的特征是運(yùn)用了預(yù)流來(lái)加快運(yùn)算。預(yù)流說(shuō)明圖中的節(jié)點(diǎn)(除s,t)，僅需要滿足流入量=流出量。其中流入量流出量的結(jié)點(diǎn)，我們稱(chēng)之為活動(dòng)節(jié)點(diǎn)。我們的算法就是不斷地將活動(dòng)結(jié)點(diǎn)，變?yōu)榉腔顒?dòng)結(jié)點(diǎn)，使得預(yù)流成為可行流。,預(yù)流推進(jìn)算法流程,算法過(guò)程prepare()，即首先將與s相連的邊設(shè)為滿流，并將這時(shí)產(chǎn)生的活動(dòng)結(jié)點(diǎn)加入隊(duì)列Q。這是算法的開(kāi)始。以后便重復(fù)以下過(guò)程直到Q為空：(1).選出Q的一個(gè)活動(dòng)頂點(diǎn)u。并依次判斷殘量網(wǎng)絡(luò)G中每條邊(u,v)，若h(u)=h(v)+1，則順著這里條邊推流，直到Q變成非活動(dòng)結(jié)點(diǎn)（不存在多余流量）。(Push推流過(guò)程)(2).如果u還是活動(dòng)結(jié)點(diǎn)。則需要對(duì)u進(jìn)行重新標(biāo)號(hào)：h(u)=minh(v)+1，其中邊(u,v)存在于G中。然后再將u加入隊(duì)列。(relable過(guò)程)可以證明，通過(guò)以上算法得到的結(jié)果就是最大流。,預(yù)流推進(jìn)算法示例,頂點(diǎn)u的通過(guò)量g(u)：剩余圖中，找入邊權(quán)和與出邊權(quán)和的較小值增廣時(shí)，每次找一個(gè)通過(guò)量最小的點(diǎn)v，從點(diǎn)v向源點(diǎn)“推”大小為g(v)的流量向匯點(diǎn)“拉”大小為g(v)的流量盡量使剩余圖中的邊飽和,用預(yù)流推進(jìn)方法的一些網(wǎng)絡(luò)流算法,預(yù)流推進(jìn)的算法核心思想是以邊為單元進(jìn)行推流操作：一般的預(yù)流推進(jìn)算法：在剩余圖中，維護(hù)一個(gè)預(yù)流，不斷對(duì)活躍點(diǎn)執(zhí)行push操作，或者relable操作來(lái)重新調(diào)整這個(gè)預(yù)流，直到不能操作。O(nm2)先進(jìn)先出預(yù)流推進(jìn)算法：在剩余圖中，以先進(jìn)先出隊(duì)列維護(hù)活躍點(diǎn)。O(n3)最高標(biāo)號(hào)預(yù)流推進(jìn)算法：在剩余圖中，每次檢查最高標(biāo)號(hào)的活躍點(diǎn)，需要用到優(yōu)先隊(duì)列。O(n2m1/2),費(fèi)用流,流最重要的應(yīng)用是盡可能多的分流物資，這也就是我們已經(jīng)研究過(guò)的最大流問(wèn)題。然而實(shí)際生活中，最大配置方案肯定不止一種，一旦有了選擇的余地，費(fèi)用的因素就自然參與到?jīng)Q策中來(lái)。右圖是一個(gè)最簡(jiǎn)單的例子：弧上標(biāo)的兩個(gè)數(shù)字第一個(gè)是容量，第二個(gè)是費(fèi)用。這里的費(fèi)用是單位流量的花費(fèi)，譬如fs1=4，所需花費(fèi)為3*4=12。容易看出，此圖的最大流（流量是8）為：fs1=f1t=5,fs2=f2t=3。所以它的費(fèi)用是：3*5+4*5+7*3+2*3=62。,費(fèi)用流定義,設(shè)有帶費(fèi)用的網(wǎng)絡(luò)流圖G=(V,E,C,W)，每條弧對(duì)應(yīng)兩個(gè)非負(fù)整數(shù)Cij、Wij，表示該弧的容量和費(fèi)用。若流f滿足：流量V(f)最大。滿足a的前提下，流的費(fèi)用Cost(f)=E(fij*Wij)最小。就稱(chēng)f是網(wǎng)絡(luò)流圖G的最小費(fèi)用最大流。最小費(fèi)用可改進(jìn)路設(shè)P是流f的可改進(jìn)路，定義P+Wij-P-Wij為P的費(fèi)用(為什么如此定義？)如果P是關(guān)于f的可改進(jìn)路中費(fèi)用最小的，就稱(chēng)P是f的最小費(fèi)用可改進(jìn)路。,費(fèi)用流算法,求最小費(fèi)用最大流的基本思想是貪心法。即：對(duì)于流f，每次選擇最小費(fèi)用可改進(jìn)路進(jìn)行改進(jìn)，直到不存在可改進(jìn)路為止。這樣的得到的最大流必然是費(fèi)用最小的。算法可描述為：第1步.令f為零流。第2步.若無(wú)最小費(fèi)用可改進(jìn)路，轉(zhuǎn)第5步；否則找到最小費(fèi)用可改進(jìn)路，設(shè)為P。第3步.根據(jù)P求delta（改進(jìn)量）。第4步.放大f。轉(zhuǎn)第2步。第5步.算法結(jié)束。此時(shí)的f即最小費(fèi)用最大流。,如何求最小費(fèi)用可改進(jìn)路,設(shè)帶費(fèi)用的網(wǎng)絡(luò)流圖G=(V,E,C,W)，它的一個(gè)可行流是f。我們構(gòu)造帶權(quán)有向圖B=(V,E)，其中：V=V。若E，fijE，權(quán)為Wij。若E，fij0，那么E，權(quán)為-Wij。顯然，B中從S到T的每一條道路都對(duì)應(yīng)關(guān)于f的一條可改進(jìn)路；反之，關(guān)于f的每條可改進(jìn)路也能對(duì)應(yīng)B中從S到T的一條路徑。即兩者存在一一映射的邏輯關(guān)系。故若B中不存在從S到T的路徑，則f必然沒(méi)有可改進(jìn)路；不然，B中從S到T的最短路徑即為f的最小費(fèi)用可改進(jìn)路?，F(xiàn)在的問(wèn)題變成：給定帶權(quán)有向圖B=(V,E)，求從S到T的一條最短路徑。,迭代法求最短路經(jīng),考慮到圖中存在權(quán)值為負(fù)數(shù)的弧，不能采用Dijkstra算法；Floyd算法的效率又不盡如人意所以，這里采用一種折衷的算法：迭代法（bellman算法）。設(shè)Shorti表示從S到i頂點(diǎn)的最短路徑長(zhǎng)度；從S到頂點(diǎn)i的最短路徑中，頂點(diǎn)i的前趨記為L(zhǎng)asti。那么迭代算法描述如下：（為了便于描述，令n=|V|，S的編號(hào)為0，T的編號(hào)為n+1）step1.令Shorti+（1in+1），Short00。step2.遍歷每一條弧。若Shorti+，同時(shí)Lastji。重復(fù)做step2直到不存在任何任何弧滿足此條件為止。step3.算法結(jié)束。若Shortn+1=+，則不存在從S到T的路徑；否則可以根據(jù)Last記錄的有關(guān)信息得到最短路徑。一次迭代算法的時(shí)間復(fù)雜度為O(kn2)，其中k是一個(gè)不大于n的變量。在費(fèi)用流的求解過(guò)程中，k大部分情況下都遠(yuǎn)小于n。,思維發(fā)散與探索,可改進(jìn)路費(fèi)用：“遞增！遞增？”設(shè)f從零流到最大流共被改進(jìn)了k次，每i次選擇的可改進(jìn)路的費(fèi)用為pi，那么會(huì)不會(huì)有p1p2p3pk呢？迭代法：“小心死循環(huán)！嘿嘿”迭代法會(huì)出現(xiàn)死循環(huán)嗎？也就是說(shuō)，構(gòu)造的帶權(quán)有向圖B中會(huì)存在負(fù)回路嗎？費(fèi)用：“你在乎我是負(fù)數(shù)嗎？”容量：“我管的可不僅是弧。”網(wǎng)絡(luò)流圖中的“容量”都是對(duì)弧而言的，但若是給每個(gè)頂點(diǎn)也加上一個(gè)容量限制：即通過(guò)此頂點(diǎn)的流量的上限；任務(wù)仍然是求從S到T的最小費(fèi)用最大流。你能解決嗎？,有上下界的最大流,上面討論的網(wǎng)絡(luò)流都只對(duì)每條弧都限定了上界（其實(shí)其下界可以看成0），現(xiàn)在給每條弧加上一個(gè)下界限制Aij(即必須滿足Aijfij)?；∩蠑?shù)字對(duì)第一個(gè)是上界，第二個(gè)是下界。若是撇開(kāi)下界不看，此圖的最大流如圖所示，流量是6；但若是加入了下界的限制，它的最大流量就只有5了。,怎樣找可行流,一種自然的想法是去掉下界，將其轉(zhuǎn)化為只含上界的網(wǎng)絡(luò)流圖。這種美好的愿望是可以實(shí)現(xiàn)的。具體方法如下：設(shè)原網(wǎng)絡(luò)流圖為G=(V,E,C,A)，構(gòu)造不含下界的網(wǎng)絡(luò)流圖G=(V,E,C)：V=VS,T對(duì)每個(gè)頂點(diǎn)x，令h-(x)=EAiX，若h-(x)0，就添加一條弧，其上界為h-(x)。對(duì)每個(gè)頂點(diǎn)x，令h+(x)=EAXi，若h+(x)0，就添加一條弧，其上界為h+(x)。對(duì)于任何E，都有E，其上界Cij=CijAij。新增E，其上界CTS=+。在G中以S為源點(diǎn)、T為匯點(diǎn)求得最大流f。若f中從S發(fā)出的任意一條弧是非飽和弧，則原網(wǎng)絡(luò)流圖沒(méi)有可行流。否則可得原圖的一個(gè)可行流f=f+A，即所有的fij=fij+Aij。然后再求可改進(jìn)路（反向弧必須滿足fijAij，而非fij0），不斷放大f，直到求出最大流。,另外一種構(gòu)圖方法,C(u,v)=C(u,v)-B(u,v)設(shè)如果M(i)非負(fù)，那么設(shè)一附加源S0，則可以令C(S0,i)=M(i)。如果M(i)非負(fù)，那么設(shè)一附加匯T0，則可以令C(S0,i)=-M(i)。在這樣一個(gè)加入附加源和附加匯的流網(wǎng)絡(luò)C中，如果任意g(S0,i)或g(i,T0)都達(dá)到滿載，那么C中的這一個(gè)可行流g一定對(duì)應(yīng)原網(wǎng)絡(luò)G中的一個(gè)可行流f；反之G中的任意一個(gè)可行流f都可以對(duì)應(yīng)C中的一個(gè)g(S0,i)或g(i,T0)都滿載的流。,思考？,在一個(gè)容量有上下界的流網(wǎng)絡(luò)G中，怎樣盡快求源點(diǎn)s到匯點(diǎn)t的一個(gè)可行的最大流？在一個(gè)容量有上下界的流網(wǎng)絡(luò)G中，怎樣盡快求源點(diǎn)s到匯點(diǎn)t的一個(gè)可行的最小流？,多源點(diǎn)、多匯點(diǎn)的最大流,已知網(wǎng)絡(luò)流圖有n個(gè)源點(diǎn)S1、S2、Sn，m個(gè)匯點(diǎn)T1、T2、Tm，求該圖的最大流。這樣的問(wèn)題稱(chēng)為多源點(diǎn)、多匯點(diǎn)最大流。它的解決很簡(jiǎn)單：增設(shè)一個(gè)“超級(jí)源”S，對(duì)每個(gè)源點(diǎn)Si，新增弧，容量為無(wú)窮大。增設(shè)一個(gè)“超級(jí)匯”T，對(duì)每個(gè)匯點(diǎn)Ti，新增弧，容量為無(wú)窮大。以S為源點(diǎn)、T為匯點(diǎn)求最大流f。將f中的S和T去掉，即為原圖的最大流。,頂點(diǎn)有容量限制的最大流,對(duì)除源點(diǎn)和匯點(diǎn)之外的每個(gè)頂點(diǎn)i拆分成兩個(gè)頂點(diǎn)i和i。新增一條弧，其容量為點(diǎn)i的流量限制。對(duì)于原圖中的弧，我們將其變換成。對(duì)變換后的圖求最大流即可。這里我們運(yùn)用到了化歸的思想：將未知的“點(diǎn)限制”問(wèn)題轉(zhuǎn)化為已知的“邊限制”問(wèn)題。,網(wǎng)絡(luò)流與二部圖的匹配,設(shè)二部圖為G=(X,Y,E)。增設(shè)點(diǎn)S，對(duì)于所有iX，新增弧，容量為1；增設(shè)點(diǎn)T，對(duì)于所有iY，新增一條弧，容量也為1。原圖中所有的弧予以保留，容量均為+。對(duì)新構(gòu)造出來(lái)的網(wǎng)絡(luò)流圖以S為源點(diǎn)、T為匯點(diǎn)求最大流：流量即為最大匹配數(shù)；若?。╥X，jY）的流量非零，它就是一條匹配邊。二部圖最大匹配問(wèn)題解決。那么二部圖的最佳匹配問(wèn)題又如何？仍然按照上述方法構(gòu)圖。同時(shí)令原圖中弧的費(fèi)用保持不變；新增弧的費(fèi)用置為0。然后以S為源點(diǎn)、T為匯點(diǎn)求最小費(fèi)用最大流即可。最大流的費(fèi)用即為原二部圖最佳匹配的費(fèi)用。,思考題1：餐巾問(wèn)題,某軟件公司正在規(guī)劃一項(xiàng)n天的軟件開(kāi)發(fā)計(jì)劃，根據(jù)開(kāi)發(fā)計(jì)劃第i天需要ni個(gè)軟件開(kāi)發(fā)人員，為了提高工作效率，公司給軟件人員提供了很多的服務(wù)，其中一項(xiàng)服務(wù)就是要為每個(gè)開(kāi)發(fā)人員每天提供一塊消毒毛巾，這種毛巾使用一天后必須再做消毒處理后才能使用。消毒方式有兩種，A種方式的消毒時(shí)間需要a天時(shí)間，B中方式的消毒需要b天時(shí)間（ba），A種消毒方式的費(fèi)用為每塊毛巾fA，B種消毒方式的費(fèi)用為每塊毛巾fB，而買(mǎi)一塊新毛巾的費(fèi)用為f（新毛巾是已消毒的，當(dāng)天可以使用）；而且ffAfB。公司經(jīng)理正在規(guī)劃在這n天中，每天買(mǎi)多少塊新毛巾、每天送多少塊毛巾進(jìn)行A種消毒和每天送多少塊毛巾進(jìn)行B種消毒。當(dāng)然，公司經(jīng)理希望費(fèi)用最低。你的任務(wù)就是：求出提供毛巾服務(wù)的最低總費(fèi)用。輸入文件：第1行為n,a,b,f,fA,fB.第2行為n1,n2,nn（注：1f,fA,fB60,1n1000）輸出文件：最少費(fèi)用input.txtoutput.txt412321388216,分析,公司第i天需要ni塊毛巾，可以把這ni塊毛巾的來(lái)源列舉如下：新買(mǎi)的毛巾。第ia1天之前通過(guò)A種方式消毒的毛巾。第ib1天之前通過(guò)B種方式消毒的毛巾。我們構(gòu)造帶費(fèi)用的網(wǎng)絡(luò)流圖G=(V,E,C)。V=S,V1,V2,Vn,V1,V2,Vn,T，其中S是源點(diǎn)、T是匯點(diǎn)。E中包含如下幾類(lèi)?。海?in），容量為ni，費(fèi)用為0。表示第i天需要ni塊毛巾。（1in），容量為正無(wú)窮大，費(fèi)用為f。該弧的流量表示第i天通過(guò)方式a得到的毛巾數(shù)量。（a+2in），容量為正無(wú)窮大，費(fèi)用為fA。該弧的流量表示第i天通過(guò)方式b得到的毛巾數(shù)量。（b+2in），容量為正無(wú)窮大，費(fèi)用為fB。該弧的流量表示第i天通過(guò)方式c得到的毛巾數(shù)量。（2in），容量為正無(wú)窮大，費(fèi)用為0。由于題目中沒(méi)有說(shuō)消毒完的毛巾要馬上使用，所以第3天就消毒好的毛巾可以暫且留著，到第7天、第8天再使用也可以。因此這里增設(shè)此弧。（1in），容量為ni，費(fèi)用為0。然后對(duì)這個(gè)網(wǎng)絡(luò)流圖以S為源點(diǎn)、T為匯點(diǎn)的求最小費(fèi)用最大流即可。求得的最大流費(fèi)用就是原問(wèn)題的答案。,思考題2：Agent,有n名雙重間諜潛伏在敵軍內(nèi)部，分別編號(hào)為1,2,3,n。在給定的時(shí)間內(nèi)，任意兩人之間至多只進(jìn)行一次點(diǎn)對(duì)點(diǎn)的雙人聯(lián)系。數(shù)據(jù)將給你一份表格，表格中將提供任意兩位間諜i和j之間進(jìn)行聯(lián)系的安全程度，用一個(gè)0，1的實(shí)數(shù)Sij表示；以及他們聯(lián)系時(shí)，能夠互相傳遞的消息的最大數(shù)目，用一個(gè)正整數(shù)表示Mij。（如果在表格中沒(méi)有被提及，那么間諜i和j之間不進(jìn)行直接聯(lián)系）。假消息從盟軍總部傳遞到每個(gè)間諜手里的渠道也不是絕對(duì)安全的，我們用0，1的實(shí)數(shù)ASj表示總部與間諜j之間進(jìn)行聯(lián)系的安全程度，AMj則表示總部和間諜j之間進(jìn)行聯(lián)系時(shí)傳遞的消息的最大數(shù)目。對(duì)于不和總部直接聯(lián)系的間諜，他的AMj=0（而表格中給出的他的ASj是沒(méi)有意義的）。,當(dāng)然，假消息從間諜手中交到敵軍的情報(bào)部官員的辦公桌上的過(guò)程是絕對(duì)安全的，也就是說(shuō)，間諜與敵軍情報(bào)部門(mén)之間要么不進(jìn)行聯(lián)系，要么其聯(lián)系的安全程度是1（即完全可靠）?，F(xiàn)在我軍司令部想利用這些間諜將k條假消息發(fā)布到敵軍情報(bào)機(jī)關(guān)的負(fù)責(zé)人。消息先由總部一次性發(fā)給n名間諜中的一些人，再通過(guò)它們之間的情報(bào)網(wǎng)傳播，最終由這n名間諜中某些人將情報(bào)送到敵軍手中。對(duì)于一條消息，只有安全的通過(guò)了所有的中轉(zhuǎn)過(guò)程到達(dá)敵軍情報(bào)部，這個(gè)傳遞消息的過(guò)程才算安全的；因此根據(jù)乘法原理，它的安全程度P就是從總部出發(fā)，經(jīng)多次傳遞直到到達(dá)敵軍那里，每一次傳遞該消息的安全程度的乘積。而對(duì)于整個(gè)計(jì)劃而言，只有當(dāng)k條消息都安全的通過(guò)情報(bào)網(wǎng)到達(dá)敵軍手中，沒(méi)有一條引起懷疑時(shí)，才算是成功的。所以計(jì)劃的可靠程度是所有消息的安全程度的乘積。顯然，計(jì)劃的可靠性取決于這些消息在情報(bào)網(wǎng)中的傳遞方法。你的任務(wù)是：擬定一個(gè)方案，確定消息應(yīng)該從那些人手中傳遞到那些人手中，使得最終計(jì)劃的可靠性最大。,輸入文件：第一行:兩個(gè)整數(shù)N和K，分別是間諜的總?cè)藬?shù)和計(jì)劃包含的消息總數(shù)。第二行:2n個(gè)數(shù)，前n個(gè)數(shù)實(shí)數(shù)AS1,AS2,ASn（范圍在0,1以內(nèi)）;后n個(gè)數(shù)是整數(shù)AM1,AM2,AMn。第三行:n個(gè)整數(shù)，其中第i（i=1,2,n）個(gè)整數(shù)如果為0表示間諜i與敵軍情報(bào)部不進(jìn)行聯(lián)系，如果為1則表示間諜與敵軍情報(bào)部進(jìn)行聯(lián)系。第四行開(kāi)始，每行包括4個(gè)數(shù)，依次分別是：代表間諜編號(hào)的正整數(shù)i和j，間諜i和j聯(lián)系的安全性參數(shù)Sij（0,1范圍內(nèi)的實(shí)數(shù)），以及i、j之間傳遞的最大消息數(shù)Mij（每以行的i均小于j）。最后一行包含兩個(gè)整數(shù)-11，表示輸入數(shù)據(jù)的結(jié)束。0n300,0k300。輸出文件：輸出文件中只有一行。這一行中包含一個(gè)實(shí)數(shù)P，給出的是整個(gè)計(jì)劃的可靠程度P，保留5位有效數(shù)字（四舍五入）。如果情報(bào)根本不能將K條消息傳到敵軍手中，那么計(jì)劃的可靠性為0。（你可以假定，如果計(jì)劃存在，那么它的可靠性大于1e-12）,輸入輸出樣例Agent.inAgent.out6130.000211840.90.70.8000268000000101140.52230.95250.82260.87350.82560.84-1-1,分析,題目中的“總部”、“敵軍情報(bào)部”與“間諜”的地位是完全相等的，為了方便敘述可以將兩者亦看作是間諜：“總部”編號(hào)為0、“敵軍情報(bào)部”編號(hào)為n+1。那么S0i=ASi，M0i=AMi；若間諜i可以與敵軍司令部直接聯(lián)系Si,n+1=1,Mi,n+1=+，否則Si,n+1=0,Mi,n+1=0。我們構(gòu)造帶費(fèi)用的網(wǎng)絡(luò)流圖G=(V,E,M,S)。（M為容量，S位費(fèi)用）第i個(gè)間諜抽象成頂點(diǎn)i，另外增加匯點(diǎn)T。所有頂點(diǎn)構(gòu)成的集合記為V。若Mij0，則存在弧和：其容量皆為Mij；費(fèi)用Sji=Sij=ln(Sij)。增設(shè)弧，其容量為k，費(fèi)用為0。然后以V0為源點(diǎn)、T為匯點(diǎn)求最大費(fèi)用最大流。若流量小于k，則不存在可行方案不然則最大可靠性為：,證明,設(shè)最大費(fèi)用最大流的費(fèi)用為Cost，那么：因?yàn)镃ost達(dá)到最大，所以可靠性也達(dá)到最大。證畢。,思考題3：Plan問(wèn)題,某軟件公司有n個(gè)可選的程序項(xiàng)目，其中第i個(gè)項(xiàng)目需要耗費(fèi)資金ai元，開(kāi)發(fā)成功后可獲收益bi元。當(dāng)然，程序項(xiàng)目之間不是獨(dú)立的：開(kāi)發(fā)第i個(gè)項(xiàng)目前，必須先開(kāi)發(fā)出一些其他的項(xiàng)目（正如開(kāi)發(fā)Office前必須開(kāi)發(fā)Windows）。這些項(xiàng)目就稱(chēng)為第i個(gè)項(xiàng)目的“前趨項(xiàng)目”?，F(xiàn)在給出所有項(xiàng)目的ai、bi，以及前趨項(xiàng)目。你的任務(wù)是：幫助該公司從這n個(gè)程序項(xiàng)目中選擇若干個(gè)進(jìn)行開(kāi)發(fā)，使得總收益最大。輸入文件：輸入文件有n+3行。第1行包含一個(gè)整數(shù)n（1n200）。第2行有n個(gè)正整數(shù)a1,a2,an。第3行有n個(gè)正整數(shù)b1,b2,bn。第i+3行（1in）包含若干正整數(shù)：ri,k1,k2,kri。第一個(gè)數(shù)ri表示第i個(gè)項(xiàng)目共有多少前趨項(xiàng)目；接下來(lái)有ri個(gè)正整數(shù)k1,k2,kri，分別表示每個(gè)前趨項(xiàng)目的編號(hào)。輸出文件：輸出文件只有一個(gè)整數(shù)max，表示最大收益。,分析,令di=biai，A=i|di0，B=i|di，容量為di。對(duì)所有的iB，存在弧，容量為|di|。若第i個(gè)項(xiàng)目的某前趨項(xiàng)目編號(hào)為j，則存在弧，容量為+。然后對(duì)此網(wǎng)絡(luò)流圖求最大流，設(shè)為f。根據(jù)f易得最小割切（U,W）（即最大流最小割定理）那么選擇的項(xiàng)目集合就是U，其最大收益即：,思考題4：最大獲利,THU集團(tuán)的CS&T公司得到了一共N個(gè)可以作為通訊信號(hào)中轉(zhuǎn)站的地址，建立第i個(gè)通訊中轉(zhuǎn)站需要的成本為Pi（1iN）。另外公司用戶群一共M個(gè)。關(guān)于第i個(gè)用戶群的信息概括為Ai,Bi和Ci：這些用戶會(huì)使用中轉(zhuǎn)站Ai和中轉(zhuǎn)站Bi進(jìn)行通訊，公司可以獲益Ci。（1iM,1Ai,BiN）THU集團(tuán)的C