

$2.$太空飞行计划问题

题目

$W$ 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合 $E={E_1，E_2，…，E_m}$ ，和进行这些实验需要使用的全部仪器的集合 $I={I_1，I_2，…I_n}$。实验 $E_j$ 需要用到的仪器是 $I$ 的子集 $R_j \subset I$。配置仪器 $I_k$ 的费用为 $c_k$ 美元。实验 $E_j$ 的赞助商已同意为该实验结果支付 $p_j$ 美元。$W$ 教授的任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。

对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划。

题解

感觉这题其实还挺神的。 模型为最大权闭合子图，可以使用最小割解决。 将实验放到左边 $X$ 集合，器材放到右边 $Y$ 集合。 $S$ 向 $X$ 集合中的点连边容量为 $p_i$ 即收入， $Y$ 集合中的点向$T$连边容量为 $c_i$ 即费用，设 $Total=\sum_{i=1}^{n} p_i$ , $Cut$ 为求出的最小割(即最大流)，那么答案为 $Total-Cut$,对应的解是最小割中的点，即增广完之后仍然可以从 $S$ 点到达的点。 接下来证明一下正确性，设集合 $A$ 为所有实验，集合 $B$ 为所有仪器，定义一个割划分出的 $S$ 集合为一个解。 那么割集的容量之和就是(未被选的 $A$ 集合中的顶点的权值 $+$ 被选的 $B$ 集合中的顶点的权值)，记为 $Cut$。 $A$ 集合中所有顶点的权值之和记为 $Total$，那么 $Total - Cut$ 就是(被选的$A$集合中的顶点的权值 $-$ 被选的$B$集合中的顶点的权值)，即为我们的目标函数，记为 $A$。 要想最大化目标函数 $A$，就要尽可能使 $Cut$ 小，$Total$ 是固定值，所以目标函数A取得最大值的时候，$Cut$最小，即为最小割。