【正文】 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。那么 S0i = ASi， M0i = AMi；若間諜 i可以與敵軍司令部直接聯(lián)系 Si,n+1=1, Mi,n+1=+∞ ，否則 Si,n+1=0, Mi,n+1=0。 ? 我們構造帶費用的網(wǎng)絡流圖 G = (V, E, M, S’) 。（ M為容量， S’位費用） ? 第 i個間諜抽象成頂點 i，另外增加匯點 T。所有頂點構成的集合記為 V。 ? 若 Mij≠0 ，則存在弧 i, j和 j, i：其容量皆為 Mij；費用 Sji’ =Sij’ = ln(S ij)。 ? 增設弧 n + 1, T，其容量為 k，費用為 0。 ? 然后以 V0為源點、 T為匯點求最大費用最大流。若流量小于 k，則不存在可行方案 ? 不然則最大可靠性為： ???? EjifijijS,證明 ? 設最大費用最大流的費用為 Cost，那么： ? 因為 Cost達到最大，所以可靠性也達到最大。證畢。 C o s tSfEjifijEjiijijEjiijijeeSSfSfC o s tEjiijijij ?????????????????????,ln,ln39。可靠性思考題 3： Plan問題 ? 某軟件公司有 n個可選的程序項目，其中第 i個項目需要耗費資金 ai元，開發(fā)成功后可獲收益 bi元。 ? 當然，程序項目之間不是獨立的：開發(fā)第 i個項目前，必須先開發(fā)出一些其他的項目（正如開發(fā) Office前必須開發(fā) Windows）。這些項目就稱為第i個項目的“前趨項目”。 ? 現(xiàn)在給出所有項目的 ai、 bi，以及前趨項目。你的任務是：幫助該公司從這 n個程序項目中選擇若干個進行開發(fā)，使得總收益最大。 ? 輸入文件： 輸入文件有 n + 3行。 第 1行包含一個整數(shù) n（ 1≤n≤200 ）。 第 2行有 n個正整數(shù) a1, a2, …, an 。 第 3行有 n個正整數(shù) b1, b2, …, bn 。 第 i + 3行（ 1≤i≤n ）包含若干正整數(shù)： ri, k1, k2, …, kri 。第一個數(shù) ri表示第 i個項目共有多少前趨項目；接下來有 ri個正整數(shù) k1, k2, …, kri ，分別表示每個前趨項目的編號。 ? 輸出文件： 輸出文件只有一個整數(shù) max，表示最大收益。 分析 ? 令 di = bi – ai， A = {i | di ≥ 0} ， B = {i | di 0}。則 di就是第i個項目的純收益， A是所有可以獲得利潤的項目集合， B是所有會導致虧損的項目集合。 ? 構造網(wǎng)絡流圖 G = (V, E, C)。 ? V中包含兩類頂點： 源點 S，匯點 T。 將第 i個項目抽象成頂點 Vi。則 V1, V2, …, V n∈V 。 ? E中包含三類?。? 對所有的 i∈A ，存在弧 S, i，容量為 di。 對所有的 i∈B ，存在弧 i, T，容量為 |di|。 若第 i個項目的某前趨項目編號為 j，則存在弧 i, j，容量為 +∞ 。 ? 然后對此網(wǎng)絡流圖求最大流，設為 f。 ? 根據(jù) f易得最小割切（ U, W）（即最大流最小割定理） ? 那么選擇的項目集合就是 U，其最大收益即： ???}{\ SUi id最大收益思考題 4： 最大獲利 ? THU集團的 CSamp。T公司得到了一共 N個可以作為通訊信號中轉站的地址，建立第 i個通訊中轉站需要的成本為 Pi（ 1≤ i≤ N）。 ? 另外公司用戶群一共 M個。關于第 i個用戶群的信息概括為 Ai, Bi和 Ci：這些用戶會使用中轉站 Ai和中轉站 Bi進行通訊，公司可以獲益 Ci。（ 1≤ i≤ M, 1≤ Ai, Bi≤ N） ? THU集團的 CSamp。T公司可以有選擇的建立一些中轉站（投入成本），為一些用戶提供服務并獲得收益（獲益之和）。那么如何選擇最終建立的中轉站才能讓公司的凈獲利最大呢？（凈獲利 = 獲益之和 投入成本之和） 【 輸入格式 】 輸入文件中第一行有兩個正整數(shù) N和 M 。 第二行中有 N個整數(shù)描述每一個通訊中轉站的建立成本，依次為 P1, P2, …, P N 。 以下 M行，第 (i + 2)行的三個數(shù) Ai, Bi和 Ci描述第 i個用戶群的信息。 【 輸出格式 】 公司可以得到的最大凈獲利。 【 數(shù)據(jù)規(guī)模和約定 】 80%的數(shù)據(jù)中： N≤ 200， M≤ 1 000。 100%的數(shù)據(jù)中： N≤ 5 000， M≤ 50 000， 0≤ Ci≤ 100，0≤ Pi≤ 100。 分析 ? ① s到用戶 i，容量為 Ci ② 用戶 i到中轉站 Ai和 Bi，容量為 ∞ ③中轉站 i到 t，容量為 Pi ? 考慮這個模型的割 割邊不可能是②中的邊，這保證了解的合法性 屬于①的割邊表示損失的利益 屬于③的割邊表示付出的代價 ? 顯然割的量越小越好，這樣這道題就轉換成一個最小割的問題 根據(jù)最大流最小割定理，設 sum=∑ Ci，我們只要求出該網(wǎng)絡的最大流 maxflow，則 summaxflow就是最大獲利 。 構圖模型 ? 建立一張共有 n+m+2個的頂點、 3*m+n條邊的二分圖，求網(wǎng)絡的最大流。 匯點 N個點 M個點 源點 思考題 5：矩陣游戲 （ 2022年江蘇省選） ? 題目大意： ? 對于一個 n行、 m列的 01矩陣，規(guī)定在第 i行中 1的個數(shù)恰為 Ri個（ 1=i=n）；在第 j列中 1的個數(shù)恰為 Cj個（ 1=j=m）。 ? 每一行、每一列最多可以有一個格子指定為 0。 ? 問是否存在一種滿足條件的 01矩陣。 ? 數(shù)據(jù)范圍： n,m=1000 每個測試點最多 10組數(shù)據(jù)。 分析 ? 把第 i行作為點 Xi，從 S至 Xi連一條邊，容量為 Ri ? 把第 j列作為點 Yj，從 Yj至 T連一條邊，容量為 Cj ? 若第 i行第 j列可以放 1，那么從 Xi至 Yj連一條邊，容量為 1 ? 求網(wǎng)絡最大流，判斷流量值是否等于 1的總數(shù)即可 ? 邊的總數(shù)達到了 O(n*m) ? 使用 MPLA可以拿到 60%的分數(shù) ? 使用 Dinic可以拿到 80%的分數(shù) ? 首先不考慮指定為 0的格子； ? 因為將某 2行或某 2列交換，不影響問題的求解，我們不妨將 Ri與 Ci從大到小排序； ? 將多余的 1儲存起來； ? 第三列，需要 5個 1， 但只有 4行可以提供 1； 深入分析 結論 ? 加入這個簡單的判斷后， MPLA算法仍然只能過 60%。 ? 但是 Dinic通過了 100%的數(shù)據(jù)。 ? 其實這題的標準方法是貪心，但使用高效的網(wǎng)絡流算法節(jié)省了大部分的思考時間。