【正文】 分析 ? 把第 i行作為點(diǎn) Xi，從 S至 Xi連一條邊，容量為 Ri ? 把第 j列作為點(diǎn) Yj，從 Yj至 T連一條邊，容量為 Cj ? 若第 i行第 j列可以放 1，那么從 Xi至 Yj連一條邊，容量為 1 ? 求網(wǎng)絡(luò)最大流，判斷流量值是否等于 1的總數(shù)即可 ? 邊的總數(shù)達(dá)到了 O(n*m) ? 使用 MPLA可以拿到 60%的分?jǐn)?shù) ? 使用 Dinic可以拿到 80%的分?jǐn)?shù) ? 首先不考慮指定為 0的格子； ? 因?yàn)閷⒛?2行或某 2列交換，不影響問題的求解，我們不妨將 Ri與 Ci從大到小排序； ? 將多余的 1儲(chǔ)存起來； ? 第三列，需要 5個(gè) 1， 但只有 4行可以提供 1； 深入分析 結(jié)論 ? 加入這個(gè)簡單的判斷后， MPLA算法仍然只能過 60%。 【 數(shù)據(jù)規(guī)模和約定 】 80%的數(shù)據(jù)中： N≤ 200， M≤ 1 000。 ? 另外公司用戶群一共 M個(gè)。 將第 i個(gè)項(xiàng)目抽象成頂點(diǎn) Vi。 第 3行有 n個(gè)正整數(shù) b1, b2, …, bn ?？煽啃运伎碱} 3： Plan問題 ? 某軟件公司有 n個(gè)可選的程序項(xiàng)目，其中第 i個(gè)項(xiàng)目需要耗費(fèi)資金 ai元，開發(fā)成功后可獲收益 bi元。（ M為容量， S’位費(fèi)用） ? 第 i個(gè)間諜抽象成頂點(diǎn) i，另外增加匯點(diǎn) T。 最后一行包含兩個(gè)整數(shù) 1 – 1，表示輸入數(shù)據(jù)的結(jié)束。所以計(jì)劃的可靠程度是所有消息的安全程度的乘積。（如果在表格中沒有被提及，那么間諜 i和 j之間不進(jìn)行直接聯(lián)系）。由于題目中沒有說消毒完的毛巾要馬上使用，所以第 3天就消毒好的毛巾可以暫且留著，到第 7天、第 8天再使用也可以。表示第 i天需要 ni塊毛巾。當(dāng)然，公司經(jīng)理希望費(fèi)用最低。 ? 二部圖最大匹配問題解決。新增一條弧 i’, i’’ ，其容量為點(diǎn) 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)都滿載的流。 Vi, Vj∈E ，都有 Vi, Vj∈E’ ，其上界 C’ ij = Cij – Aij?！? 網(wǎng)絡(luò)流圖中的“容量”都是對(duì)弧而言的，但若是給每個(gè)頂點(diǎn)也加上一個(gè)容量限制：即通過此頂點(diǎn)的流量的上限；任務(wù)仍然是求從 S到 T的最小費(fèi)用最大流。 {求改進(jìn)量 } i := n。 {找最優(yōu)可改進(jìn)路 } if best[n] = maxint then break。 more := true。 {best：最短路長度； last：可改進(jìn)路中的前趨頂點(diǎn) } more : boolean。重復(fù)做 step 2直到不存在任何任何弧滿足此條件為止。即兩者存在一一映射的邏輯關(guān)系。轉(zhuǎn)第 2步。 ? 最小費(fèi)用可改進(jìn)路 設(shè) P是流 f的可改進(jìn)路，定義 ∑ vi,vj∈P+ Wij ∑ vi,vj∈P Wij 為 P的費(fèi)用 (為什么如此定義？ ) 如果 P是關(guān)于 f的可改進(jìn)路中費(fèi)用最小的，就稱 P是 f的最小費(fèi)用可改進(jìn)路 。 ? 右圖是一個(gè)最簡單的例子：弧上標(biāo)的兩個(gè)數(shù)字第一個(gè)是容量，第二個(gè)是費(fèi)用。 中。我們的算法就是不斷地將活動(dòng)結(jié)點(diǎn)，變?yōu)榉腔顒?dòng)結(jié)點(diǎn)，使得預(yù)流成為可行流。 O(nm*logU) ? 最短增廣路方法 (MPLA)：在剩余圖中，每次任意找一條 含結(jié)點(diǎn)數(shù)最少 的增廣路徑增廣。 repeat j := i。 delta := maxint。 last[1] := maxint。 實(shí)例 復(fù)雜度分析 ? 設(shè)圖中弧數(shù)為 m,每找一條增廣軌最多需要進(jìn)行 2m次弧的檢查。 ? 定理 3：整流定理。把 P上所有與 P方向一致的弧定義為正向弧，正向弧的全體記為 P+；把 P上所有與P方向相悖的弧定義為反向弧，反向弧的全體記為 P。 3. 每一條弧都有非負(fù)數(shù)，叫做該邊的容量。圖論算法 最大流問題 長沙市雅禮中學(xué) 朱 全 民 運(yùn)輸網(wǎng)絡(luò) ? 現(xiàn)在想將一些物資從 S運(yùn)抵 T，必須經(jīng)過一些中轉(zhuǎn)站。邊 (vi, vj)的容量用 cij表示。 ? 譬如在圖中， P = (S, V1, V2, V3, V4, T)，那么 P+ = {S, V1, V1, V2, V2, V3, V4, T} P = {V4, V3} ? 給定一個(gè)可行流 f， P是從 S到 T的一條道路，如果滿足： fij是非飽和流，并且 i,j∈ P+ , f ij是非零流，并且i,j∈ P 那么就稱 P是 f的一條 可增廣路 。 如果網(wǎng)絡(luò)中所有的弧的容量是整數(shù)，則存在整數(shù)值的最大流。如果所有弧的容量為整數(shù)，則最多需要 v(其中 v為最大流 )次增廣，因此總的計(jì)算量為 O(mv)。 repeat i := 0。 i := n。 i := abs(last[j])。 O(nm2) ? 連續(xù)最短增廣路方法（ DINIC）：在剩余圖中，每次 BFS找增廣路徑增廣路徑時(shí)，記錄每個(gè)點(diǎn)的距離標(biāo)號(hào)。 預(yù)流推進(jìn)算法流程 ? 算法過程 prepare()，即首先將與 s相連的邊設(shè)為滿流，并將這時(shí)產(chǎn)生的活動(dòng)結(jié)點(diǎn)加入隊(duì)列 Q。然后再將 u加入隊(duì)列。這里的費(fèi)用是單位流量的花費(fèi)，譬如 fs1=4，所需花費(fèi)為 3*4=12。 費(fèi)用流算法 ? 求最小費(fèi)用最大流的基本思想是貪心法。 ? 第 5步 . 算法結(jié)束。 ? 故若 B中不存在從 S到 T的路徑，則 f必然沒有可改進(jìn)路；不然， B中從 S到 T的最短路徑即為 f的最小費(fèi)用可改進(jìn)路。 ? step 3. 算法結(jié)束。 begin repeat fillword(best, sizeof(best) shr 1, maxint)。 end。 delta := maxint。 repeat j := i。你能解決嗎？ 有上下界的最大流 ? 上面討論的網(wǎng)絡(luò)流都只對(duì)每條弧都限定了上界（其實(shí)其下界可以看成 0），現(xiàn)在給每條弧 Vi, Vj加上一個(gè)下界限制 Aij (即必須滿足 Aij≤f ij)。 T, S∈E’ ，其上界 CTS = +∞ 。 ?? ?? ?? EviEiu viBiuBiM ),(),( ),(),()(思考？ ? 在一個(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) S S …… 、 Sn， m個(gè)匯點(diǎn)T T …… 、 Tm，求該圖的最大流。 ? 對(duì)于原圖中的弧 i, j，我們將其變換成 i’’, j’ 。 ? 那么二部圖的最佳匹配問題又如何？ ? 仍然按照上述方法構(gòu)圖。 你的任務(wù)就是：求出提供毛巾服務(wù)的最低總費(fèi)用。 2. Vi, T（ 1≤i≤n ），容量為正無窮大，費(fèi)用為 f。因此這里增設(shè)此弧。 ? 假消息從盟軍總部傳遞到每個(gè)間諜手里的渠道也不是絕對(duì)安全的，我們用 [0， 1]的實(shí)數(shù) ASj表示總部與間諜 j之間進(jìn)行聯(lián)系的安全程度， AMj則表示總部和間諜 j之間進(jìn)行聯(lián)系時(shí)傳遞的消息的最大數(shù)目。 ? 顯然，計(jì)劃的可靠性取決于這些消息在情報(bào)網(wǎng)中的傳遞方法。