【正文】 T’ ，容量為無窮大。 ? 將 f中的 S’ 和 T’ 去掉，即為原圖的最大流。新增一條弧 i’, i’’ ，其容量為點 i的流量限制。 ? 對變換后的圖求最大流即可。 網(wǎng)絡(luò)流與二部圖的匹配 ? 設(shè)二部圖為 G = (X, Y, E)。原圖中所有的弧予以保留，容量均為 +∞ 。 ? 二部圖最大匹配問題解決。同時令原圖中弧的費用保持不變；新增弧的費用臵為 0。最大流的費用即為原二部圖最佳匹配的費用。消毒方式有兩種， A種方式的消毒時間需要 a天時間， B中方式的消毒需要 b天時間（ ba），A種消毒方式的費用為每塊毛巾 fA， B種消毒方式的費用為每塊毛巾 fB，而買一塊新毛巾的費用為 f（新毛巾是已消毒的，當(dāng)天可以使用）；而且 ffAfB。當(dāng)然，公司經(jīng)理希望費用最低。 ? 輸入文件：第 1行為 n, a, b, f, fA, fB. 第 2行為 n1, n2, …, n n（注： 1≤f, fA, fB≤60, 1≤n≤1000 ） ? 輸出文件：最少費用 4 1 2 3 2 1 38 8 2 1 6 分析 ? 公司第 i天需要 ni 塊毛巾，可以把這 ni 塊毛巾的來源列舉如下： 新買的毛巾。 第 i – b – 1天之前通過 B種方式消毒的毛巾。 V = {S, V1, V2, …, V n, V1’, V2’, …, V n’, T} ，其中 S是源點、 T是匯點。表示第 i天需要 ni塊毛巾。該弧的流量表示第 i天通過方式 a得到的毛巾數(shù)量。該弧的流量表示第 i天通過方式 b得到的毛巾數(shù)量。該弧的流量表示第 i天通過方式 c得到的毛巾數(shù)量。由于題目中沒有說消毒完的毛巾要馬上使用，所以第 3天就消毒好的毛巾可以暫且留著，到第 7天、第 8天再使用也可以。 6. Vi’, T （ 1≤i≤n ），容量為 ni，費用為 0。求得的最大流費用就是原問題的答案。在給定的時間內(nèi)，任意兩人之間至多只進行一次點對點的雙人聯(lián)系。（如果在表格中沒有被提及，那么間諜 i和 j之間不進行直接聯(lián)系）。對于不和總部直接聯(lián)系的間諜，他的AMj=0（而表格中給出的他的 ASj是沒有意義的）。 ? 現(xiàn)在我軍司令部想利用這些間諜將 k條假消息發(fā)布到敵軍情報機關(guān)的負責(zé)人。 ? 對于一條消息，只有安全的通過了所有的中轉(zhuǎn)過程到達敵軍情報部，這個傳遞消息的過程才算安全的；因此根據(jù)乘法原理，它的安全程度 P就是從總部出發(fā)，經(jīng)多次傳遞直到到達敵軍那里，每一次傳遞該消息的安全程度的乘積。所以計劃的可靠程度是所有消息的安全程度的乘積。 ? 你的任務(wù)是：擬定一個方案，確定消息應(yīng)該從那些人手中傳遞到那些人手中，使得最終計劃的可靠性最大。 第二行 :2n個數(shù)，前 n個數(shù)實數(shù) AS1, AS2, …, ASn （范圍在 [0, 1]以內(nèi)） 。 第三行 :n個整數(shù)，其中第 i（ i = 1, 2, …, n ）個整數(shù)如果為 0表示間諜 i與敵軍情報部不進行聯(lián)系，如果為 1則表示間諜與敵軍情報部進行聯(lián)系。 最后一行包含兩個整數(shù) 1 – 1，表示輸入數(shù)據(jù)的結(jié)束。 ? 輸出文件： 輸出文件中只有一行。 如果情報根本不能將 K條消息傳到敵軍手中，那么計劃的可靠性為 0。那么 S0i = ASi， M0i = AMi；若間諜 i可以與敵軍司令部直接聯(lián)系 Si,n+1=1, Mi,n+1=+∞ ，否則 Si,n+1=0, Mi,n+1=0。（ M為容量， S’位費用） ? 第 i個間諜抽象成頂點 i，另外增加匯點 T。 ? 若 Mij≠0 ，則存在弧 i, j和 j, i：其容量皆為 Mij；費用 Sji’ =Sij’ = ln(S ij)。 ? 然后以 V0為源點、 T為匯點求最大費用最大流。證畢。可靠性思考題 3： Plan問題 ? 某軟件公司有 n個可選的程序項目，其中第 i個項目需要耗費資金 ai元，開發(fā)成功后可獲收益 bi元。這些項目就稱為第i個項目的“前趨項目”。你的任務(wù)是：幫助該公司從這 n個程序項目中選擇若干個進行開發(fā)，使得總收益最大。 第 1行包含一個整數(shù) n（ 1≤n≤200 ）。 第 3行有 n個正整數(shù) b1, b2, …, bn 。第一個數(shù) ri表示第 i個項目共有多少前趨項目；接下來有 ri個正整數(shù) k1, k2, …, kri ，分別表示每個前趨項目的編號。 分析 ? 令 di = bi – ai， A = {i | di ≥ 0} ， B = {i | di 0}。 ? 構(gòu)造網(wǎng)絡(luò)流圖 G = (V, E, C)。 將第 i個項目抽象成頂點 Vi。 ? E中包含三類?。? 對所有的 i∈A ，存在弧 S, i，容量為 di。 若第 i個項目的某前趨項目編號為 j，則存在弧 i, j，容量為 +∞ 。 ? 根據(jù) f易得最小割切（ U, W）（即最大流最小割定理） ? 那么選擇的項目集合就是 U，其最大收益即： ???}{\ SUi id最大收益思考題 4： 最大獲利 ? THU集團的 CSamp。 ? 另外公司用戶群一共 M個。（ 1≤ i≤ M, 1≤ Ai, Bi≤ N） ? THU集團的 CSamp。那么如何選擇最終建立的中轉(zhuǎn)站才能讓公司的凈獲利最大呢？（凈獲利 = 獲益之和 投入成本之和） 【 輸入格式 】 輸入文件中第一行有兩個正整數(shù) N和 M 。 以下 M行，第 (i + 2)行的三個數(shù) Ai, Bi和 Ci描述第 i個用戶群的信息。 【 數(shù)據(jù)規(guī)模和約定 】 80%的數(shù)據(jù)中： N≤ 200， M≤ 1 000。 分析 ? ① s到用戶 i，容量為 Ci ② 用戶 i到中轉(zhuǎn)站 Ai和 Bi，容量為 ∞ ③中轉(zhuǎn)站 i到 t，容量為 Pi ? 考慮這個模型的割 割邊不可能是②中的邊，這保證了解的合法性 屬于①的割邊表示損失的利益 屬于③的割邊表示付出的代價 ? 顯然割的量越小越好，這樣這道題就轉(zhuǎn)換成一個最小割的問題 根據(jù)最大流最小割定理，設(shè) sum=∑ Ci，我們只要求出該網(wǎng)絡(luò)的最大流 maxflow，則 summaxflow就是最大獲利 。 匯點 N個點 M個點 源點 思考題 5：矩陣游戲 （ 2022年江蘇省選） ? 題目大意： ? 對于一個 n行、 m列的 01矩陣，規(guī)定在第 i行中 1的個數(shù)恰為 Ri個（ 1=i=n）；在第 j列中 1的個數(shù)恰為 Cj個（ 1=j=m）。 ? 問是否存在一種滿足條件的 01矩陣。 分析 ? 把第 i行作為點 Xi，從 S至 Xi連一條邊，容量為 Ri ? 把第 j列作為點 Yj，從 Yj至 T連一條邊，容量為 Cj ? 若第 i行第 j列可以放 1，那么從 Xi至 Yj連一條邊，容量為 1 ? 求網(wǎng)絡(luò)最大流，判斷流量值是否等于 1的總數(shù)即可 ? 邊的總數(shù)達到了 O(n*m) ? 使用 MPLA可以拿到 60%的分數(shù) ? 使用 Dinic可以拿到 80%的分數(shù) ? 首先不考慮指定為 0的格子； ? 因為將某 2行或某 2列交換，不影響問題的求解，我們不妨將 Ri與 Ci從大到小排序； ? 將多余的 1儲存起來； ? 第三列，需要 5個 1， 但只有 4行可以提供 1； 深入分析 結(jié)論 ? 加入這個簡單的判斷后， MPLA算法仍然只能過 60%。 ? 其實這題的標準方法是貪心，但使用高效的網(wǎng)絡(luò)流算法節(jié)省了大部分的