【问题分析】

最大权闭合图问题，可以转化成最小割问题，进而用最大流解决。

【建模方法】

把每个实验看作二分图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