本文正體字版由OpenCC轉換

【問題分析】

最大權閉合圖問題，可以轉化成最小割問題，進而用最大流解決。

【建模方法】

把每個實驗看作二分圖X集合中的頂點，每個設備看作二分圖Y集合中的頂點，增加源S和匯T。 1、從S向每個Xi連接一條容量爲該點收入的有向邊。 2、從Yi向T連接一條容量爲該點支出的有向邊。 3、如果一個實驗i需要設備j，連接一條從Xi到Yj容量爲無窮大的有向邊。

統計出所有實驗的收入只和Total，求網絡最大流Maxflow，最大收益就是Total-Maxflow。對應的解就是最小割劃分出的S集合中的點，也就是最後一次增廣找到阻塞流時能從S訪問到的頂點。

【建模分析】

定義一個割劃分出的S集合爲一個解，那麼割集的容量之和就是(未被選的A集合中的頂點的權值 + 被選的B集合中的頂點的權值)，記爲Cut。A集合中所有頂點的權值之和記爲Total，那麼Total - Cut就是(被選的A集合中的頂點的權值 - 被選的B集合中的頂點的權值)，即爲我們的目標函數，記爲A。要想最大化目標函數A，就要儘可能使Cut小，Total是固定值，所以目標函數A取得最大值的時候，Cut最小，即爲最小割。

該問題的一般模型爲最大權閉合圖，相關討論見《最小割模型在信息學競賽中的應用》作者胡伯濤。

太空飛行計劃問題
問題描述: W 教授正在爲國家航天中心計劃一系列的太空飛行。每次太空飛行可進行一系列商業性實驗而獲取利潤。現已確定了一個可供選擇的實驗集合 E={E1,E2,...,Em},和進行這 些實驗需要使用的全部儀器的集合 I={I1,I2,...In}。實驗 Ej 需要用到的儀器是 I 的子集 RjÕI。 配置儀器 Ik 的費用爲 ck 美元。實驗 Ej 的贊助商已同意爲該實驗結果支付 pj 美元。W 教授的 任務是找出一個有效算法,確定在一次太空飛行中要進行哪些實驗並因此而配置哪些儀器才 能使太空飛行的淨收益最大。這裏淨收益是指進行實驗所獲得的全部收入與配置儀器的全部 費用的差額。

 ́編程任務: 對於給定的實驗和儀器配置情況,編程找出淨收益最大的試驗計劃。
 ́數據輸入: 由文件 input.txt 提供輸入數據。文件第 1 行有 2 個正整數 m 和 n。m 是實驗數,n 是儀器數。接下來的 m 行,每行是一個實驗的有關數據。第一個數贊助商同意支付該實驗的費 用;接着是該實驗需要用到的若干儀器的編號。最後一行的 n 個數是配置每個儀器的費用。
 ́結果輸出:
程序運行結束時,將最佳實驗方案輸出到文件 output.txt 中。第 1 行是實驗編號;第 2 行是儀器編號;最後一行是淨收益。
輸入文件示例
input.txt
2 3
10 1 2
25 2 3
5 6 7
輸出文件示例
output.txt
1 2
1 2 3
17

上次修改時間 2017-02-03