網(wǎng)絡(luò)流算法專題ppt課件(參考版)
2025-05-15 13:11本頁面
【正文】 。 ? 但是 Dinic通過了 100%的數(shù)據(jù)。 ? 數(shù)據(jù)范圍： n,m=1000 每個測試點最多 10組數(shù)據(jù)。 ? 每一行、每一列最多可以有一個格子指定為 0。 構(gòu)圖模型 ? 建立一張共有 n+m+2個的頂點、 3*m+n條邊的二分圖，求網(wǎng)絡(luò)的最大流。 100%的數(shù)據(jù)中： N≤ 5 000， M≤ 50 000， 0≤ Ci≤ 100，0≤ Pi≤ 100。 【 輸出格式 】 公司可以得到的最大凈獲利。 第二行中有 N個整數(shù)描述每一個通訊中轉(zhuǎn)站的建立成本，依次為 P1, P2, …, P N 。T公司可以有選擇的建立一些中轉(zhuǎn)站（投入成本），為一些用戶提供服務(wù)并獲得收益（獲益之和）。關(guān)于第 i個用戶群的信息概括為 Ai, Bi和 Ci：這些用戶會使用中轉(zhuǎn)站 Ai和中轉(zhuǎn)站 Bi進(jìn)行通訊，公司可以獲益 Ci。T公司得到了一共 N個可以作為通訊信號中轉(zhuǎn)站的地址，建立第 i個通訊中轉(zhuǎn)站需要的成本為 Pi（ 1≤ i≤ N）。 ? 然后對此網(wǎng)絡(luò)流圖求最大流，設(shè)為 f。 對所有的 i∈B ，存在弧 i, T，容量為 |di|。則 V1, V2, …, V n∈V 。 ? V中包含兩類頂點： 源點 S，匯點 T。則 di就是第i個項目的純收益， A是所有可以獲得利潤的項目集合， B是所有會導(dǎo)致虧損的項目集合。 ? 輸出文件： 輸出文件只有一個整數(shù) max，表示最大收益。 第 i + 3行（ 1≤i≤n ）包含若干正整數(shù)： ri, k1, k2, …, kri 。 第 2行有 n個正整數(shù) a1, a2, …, an 。 ? 輸入文件： 輸入文件有 n + 3行。 ? 現(xiàn)在給出所有項目的 ai、 bi，以及前趨項目。 ? 當(dāng)然，程序項目之間不是獨立的：開發(fā)第 i個項目前，必須先開發(fā)出一些其他的項目（正如開發(fā) Office前必須開發(fā) Windows）。 C o s tSfEjifijEjiijijEjiijijeeSSfSfC o s tEjiijijij ?????????????????????,ln,ln39。若流量小于 k，則不存在可行方案 ? 不然則最大可靠性為： ???? EjifijijS,證明 ? 設(shè)最大費用最大流的費用為 Cost，那么： ? 因為 Cost達(dá)到最大，所以可靠性也達(dá)到最大。 ? 增設(shè)弧 n + 1, T，其容量為 k，費用為 0。所有頂點構(gòu)成的集合記為 V。 ? 我們構(gòu)造帶費用的網(wǎng)絡(luò)流圖 G = (V, E, M, S’) 。（你可以假定，如果計劃存在，那么它的可靠性大于 1e12） ? 輸入輸出樣例 ? 6 13 0 0 0 2 6 8 0 0 0 0 0 0 1 0 1 1 4 2 2 3 5 2 5 2 2 6 7 3 5 2 5 6 4 1 1 分析 ? 題目中的“總部”、“敵軍情報部”與“間諜”的地位是完全相等的，為了方便敘述可以將兩者亦看作是間諜：“總部”編號為 0、“敵軍情報部”編號為 n+1。這一行中包含一個實數(shù) P，給出的是整個計劃的可靠程度 P，保留 5位有效數(shù)字（四舍五入）。 0 n 300, 0 k 300。 第四行開始，每行包括 4個數(shù)，依次分別是：代表間諜編號的正整數(shù) i和 j，間諜 i和 j聯(lián)系的安全性參數(shù) Sij（ [0, 1]范圍內(nèi)的實數(shù)），以及 i、j之間傳遞的最大消息數(shù) Mij（每以行的 i均小于 j）。后 n個數(shù)是整數(shù) AM1, AM2, …, AMn 。 ? 輸入文件： 第一行 :兩個整數(shù) N和 K，分別是間諜的總?cè)藬?shù)和計劃包含的消息總數(shù)。 ? 顯然，計劃的可靠性取決于這些消息在情報網(wǎng)中的傳遞方法。 ? 而對于整個計劃而言，只有當(dāng) k條消息都安全的通過情報網(wǎng)到達(dá)敵軍手中，沒有一條引起懷疑時，才算是成功的。消息先由總部一次性發(fā)給 n名間諜中的一些人，再通過它們之間的情報網(wǎng)傳播，最終由這 n名間諜中某些人將情報送到敵軍手中。 ? 當(dāng)然，假消息從間諜手中交到敵軍的情報部官員的辦公桌上的過程是絕對安全的，也就是說，間諜與敵軍情報部門之間要么不進(jìn)行聯(lián)系，要么其聯(lián)系的安全程度是 1（即完全可靠）。 ? 假消息從盟軍總部傳遞到每個間諜手里的渠道也不是絕對安全的，我們用 [0， 1]的實數(shù) ASj表示總部與間諜 j之間進(jìn)行聯(lián)系的安全程度， AMj則表示總部和間諜 j之間進(jìn)行聯(lián)系時傳遞的消息的最大數(shù)目。 ? 數(shù)據(jù)將給你一份表格，表格中將提供任意兩位間諜 i和 j之間進(jìn)行聯(lián)系的安全程度，用一個 [0， 1]的實數(shù) Sij表示；以及他們聯(lián)系時，能夠互相傳遞的消息的最大數(shù)目，用一個正整數(shù)表示 Mij。 思考題 2： Agent ? 有 n名雙重間諜潛伏在敵軍內(nèi)部，分別編號為 1, 2, 3, …, n。 ? 然后對這個網(wǎng)絡(luò)流圖以 S為源點、 T為匯點的求最小費用最大流即可。因此這里增設(shè)此弧。 5. Vi’, V i1’ （ 2≤i≤n ），容量為正無窮大，費用為 0。 4. Vi, Vib1’ （ b+2≤i≤n ），容量為正無窮大，費用為 fB。 3. Vi, Via1’ （ a+2≤i≤n ），容量為正無窮大，費用為 fA。 2. Vi, T（ 1≤i≤n ），容量為正無窮大，費用為 f。 E中包含如下幾類?。? 1. S, Vi（ 1≤i≤n ），容量為 ni，費用為 0。 ? 我們構(gòu)造帶費用的網(wǎng)絡(luò)流圖 G = (V, E, C)。 第 i – a – 1天之前通過 A種方式消毒的毛巾。 你的任務(wù)就是：求出提供毛巾服務(wù)的最低總費用。公司經(jīng)理正在規(guī)劃在這 n天中，每天買多少塊新毛巾、每天送多少塊毛巾進(jìn)行 A種消毒和每天送多少塊毛巾進(jìn)行 B種消毒。 思考題 1：餐巾問題 ? 某軟件公司正在規(guī)劃一項 n天的軟件開發(fā)計劃，根據(jù)開發(fā)計劃第 i天需要ni個軟件開發(fā)人員，為了提高工作效率，公司給軟件人員提供了很多的服務(wù)，其中一項服務(wù)就是要為每個開發(fā)人員每天提供一塊消毒毛巾，這種毛巾使用一天后必須再做消毒處理后才能使用。然后以 S’ 為源點、 T’ 為匯點求最小費用最大流即可。 ? 那么二部圖的最佳匹配問題又如何？ ? 仍然按照上述方法構(gòu)圖。對新構(gòu)造出來的網(wǎng)絡(luò)流圖以 S’ 為源點、 T’ 為匯點求最大流：流量即為最大匹配數(shù)；若弧 Xi, Yj（ i∈X ， j∈Y ）的流量非零，它就是一條匹配邊。 ? 增設(shè)點 S’ ，對于所有 i∈X ，新增弧 S’, Xi ，容量為 1；增設(shè)點 T’ ，對于所有 i∈Y ，新增一條弧 Yi, T’ ，容量也為 1。 ? 這里我們運用到了化歸的思想：將未知的“點限制”問題轉(zhuǎn)化為已知的“邊限制”問題。 ? 對于原圖中的弧 i, j，我們將其變換成 i’’, j’ 。 頂點有容量限制的最大流 ? 對除源點和匯點之外的每個頂點 i拆分成兩個頂點 i’ 和 i’’ 。 ? 以 S’ 為源點、 T’ 為匯點求最大流 f。 ? 它的解決很簡單： ? 增設(shè)一個“超級源” S’ ，對每個源點 Si，新增弧 S’, Si，容量為無窮大。 ?? ?? ?? EviEiu viBiuBiM ),(),( ),(),()(思考？ ? 在一個容量有上下界的流網(wǎng)絡(luò) G中，怎
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1