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