【正文】 0 n 300, 0 k 300。所有頂點構(gòu)成的集合記為 V。 ? 當然，程序項目之間不是獨立的：開發(fā)第 i個項目前，必須先開發(fā)出一些其他的項目（正如開發(fā) Office前必須開發(fā) Windows）。 第 i + 3行（ 1≤i≤n ）包含若干正整數(shù)： ri, k1, k2, …, kri 。則 V1, V2, …, V n∈V 。關(guān)于第 i個用戶群的信息概括為 Ai, Bi和 Ci：這些用戶會使用中轉(zhuǎn)站 Ai和中轉(zhuǎn)站 Bi進行通訊，公司可以獲益 Ci。 100%的數(shù)據(jù)中： N≤ 5 000， M≤ 50 000， 0≤ Ci≤ 100，0≤ Pi≤ 100。 ? 但是 Dinic通過了 100%的數(shù)據(jù)。 ? 數(shù)據(jù)范圍： n,m=1000 每個測試點最多 10組數(shù)據(jù)。 【 輸出格式 】 公司可以得到的最大凈獲利。T公司得到了一共 N個可以作為通訊信號中轉(zhuǎn)站的地址，建立第 i個通訊中轉(zhuǎn)站需要的成本為 Pi（ 1≤ i≤ N）。 ? V中包含兩類頂點： 源點 S，匯點 T。 第 2行有 n個正整數(shù) a1, a2, …, an 。 C o s tSfEjifijEjiijijEjiijijeeSSfSfC o s tEjiijijij ?????????????????????,ln,ln39。 ? 我們構(gòu)造帶費用的網(wǎng)絡(luò)流圖 G = (V, E, M, S’) 。 第四行開始，每行包括 4個數(shù)，依次分別是：代表間諜編號的正整數(shù) i和 j，間諜 i和 j聯(lián)系的安全性參數(shù) Sij（ [0, 1]范圍內(nèi)的實數(shù)），以及 i、j之間傳遞的最大消息數(shù) Mij（每以行的 i均小于 j）。 ? 而對于整個計劃而言，只有當 k條消息都安全的通過情報網(wǎng)到達敵軍手中，沒有一條引起懷疑時，才算是成功的。 ? 數(shù)據(jù)將給你一份表格，表格中將提供任意兩位間諜 i和 j之間進行聯(lián)系的安全程度，用一個 [0， 1]的實數(shù) Sij表示；以及他們聯(lián)系時，能夠互相傳遞的消息的最大數(shù)目，用一個正整數(shù)表示 Mij。 5. Vi’, V i1’ （ 2≤i≤n ），容量為正無窮大，費用為 0。 E中包含如下幾類弧： 1. S, Vi（ 1≤i≤n ），容量為 ni，費用為 0。公司經(jīng)理正在規(guī)劃在這 n天中，每天買多少塊新毛巾、每天送多少塊毛巾進行 A種消毒和每天送多少塊毛巾進行 B種消毒。對新構(gòu)造出來的網(wǎng)絡(luò)流圖以 S’ 為源點、 T’ 為匯點求最大流：流量即為最大匹配數(shù)；若弧 Xi, Yj（ i∈X ， j∈Y ）的流量非零，它就是一條匹配邊。 頂點有容量限制的最大流 ? 對除源點和匯點之外的每個頂點 i拆分成兩個頂點 i’ 和 i’’ 。 ? 如果 M(i)非負，那么設(shè)一附加匯 T0，則可以令 C’ (S0, i) = M(i)。 x，令 h+(x)= ∑ vx,vj∈E AXi ，若 h+(x)≠0 ，就添加一條弧 x, T’ ，其上界為 h+(x) 。 思維發(fā)散與探索 ? 可改進路費用：“遞增！遞增？” 設(shè) f從零流到最大流共被改進了 k次，每 i次選擇的可改進路的費用為 pi，那么會不會有p1≤p 2≤p 3≤……≤p k呢？ ? 迭代法：“小心死循環(huán)！嘿嘿 ……” 迭代法會出現(xiàn)死循環(huán)嗎？也就是說，構(gòu)造的帶權(quán)有向圖 B中會存在負回路嗎？ ? 費用：“你在乎我是負數(shù)嗎？” ? 容量：“我管的可不僅是弧。 until i = 1。 until not more。 last[j] := i。 best, last : tline。若 Short[i] + i, j Short[j]，則令 Short[j] ? Short[i] + i, j，同時 Last[j] ? i。 ? 顯然， B中從 S到 T的每一條道路都對應(yīng)關(guān)于 f的一條可改進路；反之，關(guān)于 f的每條可改進路也能對應(yīng) B中從 S到 T的一條路徑。 ? 第 4步 . 放大 f。 就稱 f是網(wǎng)絡(luò)流圖 G的最小費用最大流。然而實際生活中，最大配臵方案肯定不止一種，一旦有了選擇的余地，費用的因素就自然參與到?jīng)Q策中來。則需要對 u進行重新標號：h(u) = min{h(v) + 1}，其中邊 (u,v)存在于 G39。其中流入量 流出量的結(jié)點，我們稱之為活動節(jié)點。 O(nmU) ? 容量縮放增廣路方法 :在剩余圖中，每次任意找一條 最大可增廣容量和 的增廣路徑增廣。 {求改進量 } i := n。 if last[n] = 0 then break。 fillchar(check, sizeof(check), false)。 ? 第 4步 (構(gòu)造最小割 )，這時現(xiàn)行流是最大的，若把所有標號的集合記為 S，所有未標號點的集合記為 T,便得到最小割 (S,T)。 ? 定理 2：可行流 f是最大流的充分必要條件是： f中不存在可改進路。 ? 定義一條道路 P，起點是 S、終點是 T。 2. 有且僅有一個頂點 T，它的出度為零，即 d+(T) = 0，這個頂點 T便稱為匯點，或稱為收點。連接中轉(zhuǎn)站的是公路，每條公路都有最大運載量。 ? 則稱之為網(wǎng)絡(luò)流圖，記為 G = (V, E, C) 可行流 可行流 對于網(wǎng)絡(luò)流圖 G，每一條弧 (i,j)都給定一個非負數(shù) fij，這一組數(shù)滿足下列三條件時稱為這網(wǎng)絡(luò)的可行流，用 f表示它。之所以稱作“可增廣”，是因為可改進路上弧的流量通過一定的規(guī)則修改，可以令整個流量放大。 ? 定理 4：最大流最小割定理。 procedure maxflow。 repeat inc(i) until (i n) or (last[i] 0) and not check[i]。 repeat j := i。 if last[j] 0 then inc(flow[i, j], delta) else dec(flow[j, i], delta)。在距離標號最短路圖上，不斷 dfs找增廣路， 即一次標號，多次增廣 。這是算法的開始。 (relable過程 ) ? 可以證明，通過以上算法得到的結(jié)果就是最大流。 ? 容易看出，此圖的最大流（流量是 8）為： fs1 = f1t = 5, fs2 = f2t = 3。即：對于流 f，每次選擇最小費用可改進路進行改進，直到不存在可改進路為止。此時的 f即最小費用最大流。 ? 現(xiàn)在的問題變成：給定帶權(quán)有向圖 B = (V’, E’) ，求從 S到 T的一條最短路徑。若 Short[n + 1]= +∞ ，則不存在從 S到 T的路徑；否則可以根據(jù) Last記錄的有關(guān)信息得到最短路徑。 fillchar(last, sizeof(last), 0)。 if (flow[j, i] 0) and (best[i] cost[j, i] best[j]) then begin best[j] := best[i] cost[j, i]。 i := n。 i := abs(last[j])。 ? 弧上數(shù)字對第一個是上界，第二個是下界。 G’ 中以 S’ 為源點、 T’ 為匯點求得最大流 f’ 。這樣的問題稱為多源點、多匯點最大流。 ? 對變換后的圖求最大流即