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