圖論算法

---最大流問題

1整理ppt運輸網絡現在想將一些物資從S運抵T，必須經過一些中轉站。連接中轉站的是公路，每條公路都有最大運載量。每條弧代表一條公路，弧上的數表示該公路的最大運載量。最多能將多少貨物從S運抵T？4248473621STV1V2V3V4公路運輸圖2整理ppt根本概念這是一個典型的網絡流模型。為了解答此題，我們先了解網絡流的有關定義和概念。假設有向圖G=(V,E)滿足以下條件：有且僅有一個頂點S，它的入度為零，即d-(S)=0，這個頂點S便稱為源點，或稱為發點。有且僅有一個頂點T，它的出度為零，即d+(T)=0，這個頂點T便稱為匯點，或稱為收點。每一條弧都有非負數，叫做該邊的容量。邊(vi,vj)的容量用cij表示。那么稱之為網絡流圖，記為G=(V,E,C)3整理ppt可行流可行流 對于網絡流圖G，每一條弧(i,j)都給定一個非負數fij，這一組數滿足以下三條件時稱為這網絡的可行流，用f表示它。1.每一條弧(i,j)有fij≤Cij2.流量平衡 除源點S和匯點T以外的所有的點vi，恒有： ∑j(fij)=∑k(fjk) 該等式說明中間點vi的流量守恒，輸入與輸出量相等。3. 對于源點S和匯點T有， ∑i(fSi)=∑j(fjT)=V(f)4整理ppt可增廣路給定一個可行流f={fij}。假設fij=Cij，稱<vi,vj>為飽和弧；否那么稱<vi,vj>為非飽和弧。假設fij=0，稱<vi,vj>為零流弧；否那么稱<vi,vj>為非零流弧。定義一條道路P，起點是S、終點是T。把P上所有與P方向一致的弧定義為正向弧，正向弧的全體記為P+；把P上所有與P方向相悖的弧定義為反向弧，反向弧的全體記為P-。譬如在圖中，P=(S,V1,V2,V3,V4,T)，那么 P+={<S,V1>,<V1,V2>,<V2,V3>,<V4,T>} P-={<V4,V3>}給定一個可行流f，P是從S到T的一條道路，如果滿足： fij是非飽和流，并且<i,j>∈P+,fij是非零流，并且<i,j>∈P- 那么就稱P是f的一條可增廣路。之所以稱作“可增廣〞，是因為可改進路上弧的流量通過一定的規那么修改，可以令整個流量放大。5整理ppt剩余圖(剩余網絡)剩余圖G’=(V,E’)流量網絡G=(V,E)中，對于任意一條邊(a,b)，假設flow(a,b)<capacity(a,b)orflow(b,a)>0那么(a,b)∈E’可以沿著a--->b方向增廣6整理ppt剩余圖中，從源點到匯點的每一條路徑都對應一條增廣路Capacity=5Capacity=6Capacity=2Flow=2Flow=2Flow=2有向圖32224剩余圖剩余圖中，每條邊都可以沿其方向增廣剩余圖的權值代表能沿邊增廣的大小7整理pptG=(V,E,C)是的網絡流圖，設U是V的一個子集，W=V\U，滿足S∈U，T∈W。即U、W把V分成兩個不相交的集合，且源點和匯點分屬不同的集合。對于弧尾在U，弧頭在W的弧所構成的集合稱之為割切，用〔U，W〕表示。把割切〔U，W〕中所有弧的容量之和叫做此割切的容量，記為C〔U，W〕，即：割切8整理ppt割切例如上例中，令U={S,V1}，那么W={V2,V3,V4,T}，那么，C(U,W)=<S,V2>+<V1,V2>+<V1,V3>+<V1,V4>=8+4+4+1=179整理ppt流量算法的根本理論定理1：對于的網絡流圖，設任意一可行流為f，任意一割切為(U,W)，必有：V(f)≤C(U,W)。定理2：可行流f是最大流的充分必要條件是：f中不存在可改進路。定理3：整流定理。 如果網絡中所有的弧的容量是整數，那么存在整數值的最大流。定理4：最大流最小割定理。 最大流等于最小割，即maxV(f)=minC(U,W)。10整理ppt最大流算法第1步，令x=(xij)是任意整數可行流，可能是零流，給s一個永久標號(-,∞)。第2步(找增廣路)，如果所有標號都已經被檢查，轉到第4步。找到一個標號但未檢查的點i,并做如下檢查，對每一個弧(i,j),如果xij<Cij,且j未標號,那么給j一個標號(+i,δ(j)),其中，δ(j)=min{Cij-xij,δ(i)}對每一個弧(j,i),如果xji>0,且j未標號，那么給j一個標號(-i,δ(j)),其中，δ(j)=min{xji,δ(i)}第3步(增廣)，由點t開始，使用指示標號構造一個增廣路,指示標號的正負那么表示通過增加還是減少弧流量來增加還是減少弧流量來增大流量，抹去s點以外的所有標號，轉第二步繼續找增廣軌。第4步(構造最小割)，這時現行流是最大的，假設把所有標號的集合記為S，所有未標號點的集合記為T,便得到最小割(S,T)。11整理ppt實例12整理ppt復雜度分析設圖中弧數為m,每找一條增廣軌最多需要進行2m次弧的檢查。如果所有弧的容量為整數，那么最多需要v(其中v為最大流)次增廣，因此總的計算量為O(mv)。13整理pptproceduremaxflow;{最大流}vari,j,delta,x:integer;last:tline;{可改進路中的前趨}check:array[0..maxn]ofboolean;{檢查數組}beginrepeatfillchar(last,sizeof(last),0);fillchar(check,sizeof(check),false);last[1]:=maxint;repeati:=0;repeatinc(i)until(i>n)or(last[i]<>0)andnotcheck[i];{找到一個已檢查而未標號的點}ifi>nthenbreak;forj:=1tondoiflast[j]=0thenifflow[i,j]<limit[i,j]thenlast[j]:=i{正向弧}elseifflow[j,i]>0thenlast[j]:=-i;{反向弧}check[i]:=true;untillast[n]<>0;

iflast[n]=0thenbreak;delta:=maxint;i:=n;repeatj:=i;i:=abs(last[j]);iflast[j]>0thenx:=limit[i,j]-flow[i,j]elsex:=flow[j,i];ifx<deltathendelta:=x;untili=1;{求改進量}i:=n;repeatj:=i;i:=abs(last[j]);iflast[j]>0theninc(flow[i,j],delta)elsedec(flow[j,i],delta);untili=1;{放大網絡流}untilfalse;end;14整理ppt利用找增廣路的其他流量算法增廣路的思想在于每次從源點搜索出一條前往匯點的增廣路，并改變路上的邊權，直到無法再進行增廣：一般增廣路方法：在剩余圖中，每次任意找一條增廣路徑增廣。O(nmU)容量縮放增廣路方法:在剩余圖中，每次任意找一條最大可增廣容量和的增廣路徑增廣。O(nm*logU)最短增廣路方法(MPLA)：在剩余圖中，每次任意找一條含結點數最少的增廣路徑增廣。O(nm2)連續最短增廣路方法〔DINIC〕：在剩余圖中，每次BFS找增廣路徑增廣路徑時，記錄每個點的距離標號。在距離標號最短路圖上，不斷dfs找增廣路，即一次標號，屢次增廣。O(n2m)15整理pptDINIC算法演示：源點匯點422532匯點32對增廣路進行增廣，增廣后退回到源點1匯點232匯點1找到增廣路路線，（紅色路線）找到增廣路路線，（紅色路線）對增廣路進行增廣，增廣后退回到源點，再無增廣路線316整理ppt用預流推進方法求網絡流預流推進算法給每一個頂點一個標號h(v)，表示該點到t的最短路〔在殘量網絡中〕。第一步hights()過程，就是BFS出初始最短路，計算出每一個頂點的h(v)。預流推進算法的特征是運用了預流來加快運算。預流說明圖中的節點(除s,t)，僅需要滿足流入量>=流出量。其中流入量>流出量的結點，我們稱之為活動節點。我們的算法就是不斷地將活動結點，變為非活動結點，使得預流成為可行流。17整理ppt預流推進算法流程算法過程prepare()，即首先將與s相連的邊設為滿流，并將這時產生的活動結點參加隊列Q。這是算法的開始。以后便重復以下過程直到Q為空：(1).選出Q的一個活動頂點u。并依次判斷殘量網絡G'中每條邊(u,v)，假設h(u)=h(v)+1，那么順著這里條邊推流，直到Q變成非活動結點〔不存在多余流量〕。(Push推流過程)(2).如果u還是活動結點。那么需要對u進行重新標號：h(u)=min{h(v)+1}，其中邊(u,v)存在于G'中。然后再將u參加隊列。(relable過程)可以證明，通過以上算法得到的結果就是最大流。18整理ppt預流推進算法例如頂點u的通過量g(u)：剩余圖中，找入邊權和與出邊權和的較小值增廣時，每次找一個通過量最小的點v，從點v向源點“推〞大小為g(v)的流量向匯點“拉〞大小為g(v)的流量盡量使剩余圖中的邊飽和34578g(u)=1219整理ppt用預流推進方法的一些網絡流算法預流推進的算法核心思想是以邊為單元進行推流操作：一般的預流推進算法：在剩余圖中，維護一個預流，不斷對活潑點執行push操作，或者relable操作來重新調整這個預流，直到不能操作。O(nm2)先進先出預流推進算法：在剩余圖中，以先進先出隊列維護活潑點。O(n3)最高標號預流推進算法：在剩余圖中，每次檢查最高標號的活潑點，需要用到優先隊列。O(n2m1/2)20整理ppt費用流流最重要的應用是盡可能多的分流物資，這也就是我們已經研究過的最大流問題。然而實際生活中，最大配置方案肯定不止一種，一旦有了選擇的余地，費用的因素就自然參與到決策中來。右圖是一個最簡單的例子：弧上標的兩個數字第一個是容量，第二個是費用。這里的費用是單位流量的花費，譬如fs1=4，所需花費為3*4=12。容易看出，此圖的最大流〔流量是8〕為：fs1=f1t=5,fs2=f2t=3。所以它的費用是：3*5+4*5+7*3+2*3=62。(6,3)(5,4)(3,7)(8,2)STV1V2費用流問題21整理ppt費用流定義設有帶費用的網絡流圖G=(V,E,C,W)，每條弧<Vi,Vj>對應兩個非負整數Cij、Wij，表示該弧的容量和費用。假設流f滿足：流量V(f)最大。滿足a的前提下，流的費用Cost(f)=∑<i,j>∈E(fij*Wij)最小。 就稱f是網絡流圖G的最小費用最大流。最小費用可改進路 設P是流f的可改進路，定義∑<vi,vj>∈P+Wij-∑<vi,vj>∈P-Wij為P的費用(為什么如此定義？) 如果P是關于f的可改進路中費用最小的，就稱P是f的最小費用可改進路。22整理ppt費用流算法求最小費用最大流的根本思想是貪心法。即：對于流f，每次選擇最小費用可改進路進行改進，直到不存在可改進路為止。這樣的得到的最大流必然是費用最小的。算法可描述為：第1步.令f為零流。第2步.假設無最小費用可改進路，轉第5步；否那么找到最小費用可改進路，設為P。第3步.根據P求delta〔改進量〕。第4步.放大f。轉第2步。第5步.算法結束。此時的f即最小費用最大流。23整理ppt如何求最小費用可改進路設帶費用的網絡流圖G=(V,E,C,W)，它的一個可行流是f。我們構造帶權有向圖B=(V’,E’)，其中：V’=V。假設<Vi,Vj>∈E，fij<Cij，那么<Vi,Vj>∈E’，權為Wij。

假設<Vi,Vj>∈E，fij>0，那么<Vj,Vi>∈E’，權為-Wij。顯然，B中從S到T的每一條道路都對應關于f的一條可改進路；反之，關于f的每條可改進路也能對應B中從S到T的一條路徑。即兩者存在一一映射的邏輯關系。故假設B中不存在從S到T的路徑，那么f必然沒有可改進路；不然，B中從S到T的最短路徑即為f的最小費用可改進路。現在的問題變成：給定帶權有向圖B=(V’,E’)，求從S到T的一條最短路徑。24整理ppt迭代法求最短路經考慮到圖中存在權值為負數的弧，不能采用Dijkstra算法；Floyd算法的效率又不盡如人意——所以，這里采用一種折衷的算法：迭代法〔bellman算法〕。設Short[i]表示從S到i頂點的最短路徑長度；從S到頂點i的最短路徑中，頂點i的前趨記為Last[i]。那么迭代算法描述如下：〔為了便于描述，令n=|V’|，S的編號為0，T的編號為n+1〕step1.令Short[i]+∞〔1≤i≤n+1〕，Short[0]0。step2.遍歷每一條弧<Vi,Vj>。假設Short[i]+<i,j><Short[j]，那么令Short[j]Short[i]+<i,j>，同時Last[j]i。重復做step2直到不存在任何任何弧滿足此條件為止。step3.算法結束。假設Short[n+1]=+∞，那么不存在從S到T的路徑；否那么可以根據Last記錄的有關信息得到最短路徑。一次迭代算法的時間復雜度為O(kn2)，其中k是一個不大于n的變量。在費用流的求解過程中，k大局部情況下都遠小于n。25整理pptprocedurecostflow;{求最小費用最大流}vari,j,x,delta:integer;best,last:tline;{best：最短路長度；last：可改進路中的前趨頂點}more:boolean;beginrepeatfillword(best,sizeof(best)shr1,maxint);fillchar(last,sizeof(last),0);last[1]:=maxint;best[1]:=0;{賦初值}repeatmore:=false;fori:=1tondoifbest[i]<>maxintthenforj:=1tondobeginif(flow[i,j]<limit[i,j])and(best[i]+cost[i,j]<best[j])thenbeginbest[j]:=best[i]+cost[i,j];last[j]:=i;more:=true;end;

if(flow[j,i]>0)and(best[i]-cost[j,i]<best[j])thenbeginbest[j]:=best[i]-cost[j,i];last[j]:=-i;more:=true;end;end;untilnotmore;{找最優可改進路}ifbest[n]=maxintthenbreak;delta:=maxint;i:=n;repeatj:=i;i:=abs(last[j]);iflast[j]>0thenx:=limit[i,j]-flow[i,j]elsex:=flow[j,i];ifx<deltathendelta:=x;untili=1;{求改進量}i:=n;repeatj:=i;i:=abs(last[j]);iflast[j]>0theninc(flow[i,j],delta)elsedec(flow[j,i],delta);untili=1;untilfalse;{根據改進量放大流}end;26整理ppt思維發散與探索可改進路費用：“遞增！遞增？〞 設f從零流到最大流共被改進了k次，每i次選擇的可改進路的費用為pi，那么會不會有p1≤p2≤p3≤……≤pk呢？迭代法：“小心死循環！嘿嘿……〞 迭代法會出現死循環嗎？也就是說，構造的帶權有向圖B中會存在負回路嗎？費用：“你在乎我是負數嗎？〞容量：“我管的可不僅是弧。〞 網絡流圖中的“容量〞都是對弧而言的，但假設是給每個頂點也加上一個容量限制：即通過此頂點的流量的上限；任務仍然是求從S到T的最小費用最大流。你能解決嗎？27整理ppt有上下界的最大流上面討論的網絡流都只對每條弧都限定了上界〔其實其下界可以看成0〕，現在給每條弧<Vi,Vj>加上一個下界限制Aij(即必須滿足Aij≤fij)。弧上數字對第一個是上界，第二個是下界。假設是撇開下界不看，此圖的最大流如下圖，流量是6；但假設是參加了下界的限制，它的最大流量就只有5了。(3,0)(3,0)(3,0)(3,0)(10,1)原問題33330(a)32231(b)增廣28整理ppt怎樣找可行流一種自然的想法是去掉下界，將其轉化為只含上界的網絡流圖。這種美好的愿望是可以實現的。具體方法如下：設原網絡流圖為G=(V,E,C,A)，構造不含下界的網絡流圖G’=(V’,E’,C’)：V’=V∪{S’,T’}對每個頂點x，令h-(x)=∑<vi,vx>∈EAiX，假設h-(x)≠0，就添加一條弧<S’,x>，其上界為h-(x)。對每個頂點x，令h+(x)=∑<vx,vj>∈EAXi，假設h+(x)≠0，就添加一條弧<x,T’>，其上界為h+(x)。對于任何<Vi,Vj>∈E，都有<Vi,Vj>∈E’，其上界C’ij=Cij–Aij。新增<T,S>∈E’，其上界CTS=+∞。在G’中以S’為源點、T’為匯點求得最大流f’。假設f’中從S’發出的任意一條弧是非飽和弧，那么原網絡流圖沒有可行流。否那么可得原圖的一個可行流f=f’+A，即所有的fij=f’ij+Aij。然后再求可改進路〔反向弧<Vi,Vj>必須滿足fij≥Aij，而非fij≥0〕，不斷放大f，直到求出最大流。29整理ppt另外一種構圖方法C’(u,v)=C(u,v)-B(u,v)設如果M(i)非負，那么設一附加源S0，那么可以令C’(S0,i)=M(i)。如果M(i)非負，那么設一附加匯T0，那么可以令C’(S0,i)=-M(i)。在這樣一個參加附加源和附加匯的流網絡C’中，如果任意g(S0,i)或g(i,T0)都到達滿載，那么C’中的這一個可行流g一定對應原網絡G中的一個可行流f；反之G中的任意一個可行流f都可以對應C’中的一個g(S0,i)或g(i,T0)都滿載的流。30整理ppt思考？在一個容量有上下界的流網絡G中，怎樣盡快求源點s到匯點t的一個可行的最大流？在一個容量有上下界的流網絡G中，怎樣盡快求源點s到匯點t的一個可行的最小流？31整理ppt多源點、多匯點的最大流網絡流圖有n個源點S1、S2、……、Sn，m個匯點T1、T2、……、Tm，求該圖的最大流。這樣的問題稱為多源點、多匯點最大流。它的解決很簡單：增設一個“超級源〞S’，對每個源點Si，新增弧<S’,Si>，容量為無窮大。增設一個“超級匯〞T’，對每個匯點Ti，新增弧<Ti,T’>，容量為無窮大。以S’為源點、T’為匯點求最大流f。將f中的S’和T’去掉，即為原圖的最大流。32整理ppt頂點有容量限制的最大流對除源點和匯點之外的每個頂點i拆分成兩個頂點i’和i’’。新增一條弧<i’,i’’>，其容量為點i的流量限制。對于原圖中的弧<i,j>，我們將其變換成<i’’,j’>。對變換后的圖求最大流即可。這里我們運用到了化歸的思想：將未知的“點限制〞問題轉化為的“邊限制〞問題。33整理ppt網絡流與二部圖的匹配設二部圖為G=(X,Y,E)。增設點S’，對于所有i∈X，新增弧<S’,Xi>，容量為1；增設點T’，對于所有i∈Y，新增一條弧<Yi,T’>，容量也為1。原圖中所有的弧予以保存，容量均為+∞。對新構造出來的網絡流圖以S’為源點、T’為匯點求最大流：流量即為最大匹配數；假設弧<Xi,Yj>〔i∈X，j∈Y〕的流量非零，它就是一條匹配邊。二部圖最大匹配問題解決。那么二部圖的最正確匹配問題又如何？仍然按照上述方法構圖。同時令原圖中弧的費用保持不變；新增弧的費用置為0。然后以S’為源點、T’為匯點求最小費用最大流即可。最大流的費用即為原二部圖最正確匹配的費用。34整理ppt思考題1：餐巾問題某軟件公司正在規劃一項n天的軟件開發方案，根據開發方案第i天需要ni個軟件開發人員，為了提高工作效率，公司給軟件人員提供了很多的效勞，其中一項效勞就是要為每個開發人員每天提供一塊消毒毛巾，這種毛巾使用一天后必須再做消毒處理后才能使用。消毒方式有兩種，A種方式的消毒時間需要a天時間，B中方式的消毒需要b天時間〔b>a〕，A種消毒方式的費用為每塊毛巾fA，B種消毒方式的費用為每塊毛巾fB，而買一塊新毛巾的費用為f〔新毛巾是已消毒的，當天可以使用〕；而且f>fA>fB。公司經理正在規劃在這n天中，每天買多少塊新毛巾、每天送多少塊毛巾進行A種消毒和每天送多少塊毛巾進行B種消毒。當然，公司經理希望費用最低。 你的任務就是：求出提供毛巾效勞的最低總費用。輸入文件：第1行為n,a,b,f,fA,fB.

第2行為n1,n2,…,nn〔注：1≤f,fA,fB≤60,1≤n≤1000〕輸出文件：最少費用 input.txtoutput.txt 41232138821635整理ppt分析公司第i天需要ni塊毛巾，可以把這ni塊毛巾的來源列舉如下：新買的毛巾。第i–a–1天之前通過A種方式消毒的毛巾。第i–b–1天之前通過B種方式消毒的毛巾。我們構造帶費用的網絡流圖G=(V,E,C)。V={S,V1,V2,…,Vn,V1’,V2’,…,Vn’,T}，其中S是源點、T是匯點。E中包含如下幾類弧：<S,Vi>〔1≤i≤n〕，容量為ni，費用為0。表示第i天需要ni塊毛巾。<Vi,T>〔1≤i≤n〕，容量為正無窮大，費用為f。該弧的流量表示第i天通過方式a得到的毛巾數量。<Vi,Vi-a-1’>〔a+2≤i≤n〕，容量為正無窮大，費用為fA。該弧的流量表示第i天通過方式b得到的毛巾數量。<Vi,Vi-b-1’>〔b+2≤i≤n〕，容量為正無窮大，費用為fB。該弧的流量表示第i天通過方式c得到的毛巾數量。<Vi’,Vi-1’>〔2≤i≤n〕，容量為正無窮大，費用為0。由于題目中沒有說消毒完的毛巾要馬上使用，所以第3天就消毒好的毛巾可以暫且留著，到第7天、第8天再使用也可以。因此這里增設此弧。<Vi’,T>〔1≤i≤n〕，容量為ni，費用為0。然后對這個網絡流圖以S為源點、T為匯點的求最小費用最大流即可。求得的最大流費用就是原問題的答案。36整理ppt思考題2：Agent有n名雙重間諜潛伏在敵軍內部，分別編號為1,2,3,…,n。在給定的時間內，任意兩人之間至多只進行一次點對點的雙人聯系。數據將給你一份表格，表格中將提供任意兩位間諜i和j之間進行聯系的平安程度，用一個[0，1]的實數Sij表示；以及他們聯系時，能夠互相傳遞的消息的最大數目，用一個正整數表示Mij。〔如果在表格中沒有被提及，那么間諜i和j之間不進行直接聯系〕。假消息從盟軍總部傳遞到每個間諜手里的渠道也不是絕對平安的，我們用[0，1]的實數ASj表示總部與間諜j之間進行聯系的平安程度，AMj那么表示總部和間諜j之間進行聯系時傳遞的消息的最大數目。對于不和總部直接聯系的間諜，他的AMj=0〔而表格中給出的他的ASj是沒有意義的〕。37整理ppt當然，假消息從間諜手中交到敵軍的情報部官員的辦公桌上的過程是絕對平安的，也就是說，間諜與敵軍情報部門之間要么不進行聯系，要么其聯系的平安程度是1〔即完全可靠〕。現在我軍司令部想利用這些間諜將k條假消息發布到敵軍情報機關的負責人。消息先由總部一次性發給n名間諜中的一些人，再通過它們之間的情報網傳播，最終由這n名間諜中某些人將情報送到敵軍手中。對于一條消息，只有平安的通過了所有的中轉過程到達敵軍情報部，這個傳遞消息的過程才算平安的；因此根據乘法原理，它的平安程度P就是從總部出發，經屢次傳遞直到到達敵軍那里，每一次傳遞該消息的平安程度的乘積。而對于整個方案而言，只有當k條消息都平安的通過情報網到達敵軍手中，沒有一條引起疑心時，才算是成功的。所以方案的可靠程度是所有消息的平安程度的乘積。顯然，方案的可靠性取決于這些消息在情報網中的傳遞方法。你的任務是：擬定一個方案，確定消息應該從那些人手中傳遞到那些人手中，使得最終方案的可靠性最大。38整理ppt輸入文件： 第一行:兩個整數N和K，分別是間諜的總人數和方案包含的消息總數。 第二行:2n個數，前n個數實數AS1,AS2,…,ASn〔范圍在[0,1]以內〕;后n個數是整數AM1,AM2,…,AMn。 第三行:n個整數，其中第i〔i=1,2,…,n〕個整數如果為0表示間諜i與敵軍情報部不進行聯系，如果為1那么表示間諜與敵軍情報部進行聯系。 第四行開始，每行包括4個數，依次分別是：代表間諜編號的正整數i和j，間諜i和j聯系的平安性參數Sij〔[0,1]范圍內的實數〕，以及i、j之間傳遞的最大消息數Mij〔每以行的i均小于j〕。 最后一行包含兩個整數-1–1，表示輸入數據的結束。 0<n<300,0<k<300。輸出文件： 輸出文件中只有一行。這一行中包含一個實數P，給出的是整個方案的可靠程度P，保存5位有效數字〔四舍五入〕。 如果情報根本不能將K條消息傳到敵軍手中，那么方案的可靠性為0。〔你可以假定，如果方案存在，那么它的可靠性大于1e-12〕39整理ppt輸入輸出樣例Agent.inAgent.out6130.000211840.90.70.8000268000000101140.52230.95250.82260.87350.82560.84-1-140整理ppt分析題目中的“總部〞、“敵軍情報部〞與“間諜〞的地位是完全相等的，為了方便表達可以將兩者亦看作是間諜：“總部〞編號為0、“敵軍情報部〞編號為n+1。那么S0i=ASi，M0i=AMi；假設間諜i可以與敵軍司令部直接聯系Si,n+1=1,Mi,n+1=+∞，否那么Si,n+1=0,Mi,n+1=0。我們構造帶費用的網絡流圖G=(V,E,M,S’)。〔M為容量，S’位費用〕第i個間諜抽象成頂點i，另外增加匯點T。所有頂點構成的集合記為V。假設Mij≠0，那么存在弧<i,j>和<j,i>：其容量皆為Mij；費用Sji’=Sij’=ln(Sij)。增設弧<n+1,T>，其容量為k，費用為0。然后以V0為源點、T為匯點求最大費用最大流。假設流量小于k，那么不存在可行方案不然那么最大可靠性為：41整理ppt證明設最大費用最大流的費用為Cost，那么：因為Cost到達最大，所以可靠性也到達最大。證畢。42整理ppt思考題3：Plan問題某軟件公司有n個可選的程序工程，其中第i個工程需要消耗資金ai元，開發成功后可獲收益bi元。當然，程序工程之間不是獨立的：開發第i個工程前，必須先開發出一些其他的工程〔正如開發Office前必須開發Windows〕。這些工程就稱為第i個工程的“前趨工程〞。現在給出所有工程的ai、bi，以及前趨工程。你的任務是：幫助該公司從這n個程序工程中選擇假設干個進行開發，使得總收益最大。輸入文件：輸入文件有n+3行。第1行包含一個整數n〔1≤n≤200〕。第2行有n個正整數a1,a2,…,an。第3行有n個正整數b1,b2,…,bn。第i+3行〔1≤i≤n〕包含假設干正整數：ri,k1,k2,…,kri。第一個數ri表示第i個工程共有多少前趨工程；接下來有ri個正整數k1,k2,…,kri，分別表示每個前趨工程的編號。輸出文件：輸出文件只有一個整數max，表示最大收益。43整理ppt分析令di=bi–ai，A={i|di≥0}，B={i|di<0}。那么di就是第i個工程的純收益，A是所有可以獲得利潤的工程集合，B是所有會導致虧損的工程集合。構造網絡流圖G=(V,E,C)。V中包含兩類頂點：源點S，匯點T。將第i個工程抽象成頂點Vi。那么V1,V2,…,Vn∈V。E中包含三類弧：對所有的i∈A，存在弧<S