1838: 太空飞行计划问题
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：5
解决：0
题目描述
W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业
性实验而获取利润。现已确定了一个可供选择的实验集合E={E1，E2，…，Em}，和进行这
些实验需要使用的全部仪器的集合I={I1，I2，…In}。实验Ej需要用到的仪器是I的子集RjÍI。
配置仪器Ik的费用为ck美元。实验Ej的赞助商已同意为该实验结果支付pj美元。W教授的
任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才
能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部
费用的差额。
对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划。
输入
第1行有2 个正整数m和n。m是实验数，n是仪
器数。接下来的m 行，每行是一个实验的有关数据。第一个数赞助商同意支付该实验的费
用；接着是该实验需要用到的若干仪器的编号。最后一行的n个数是配置每个仪器的费用。
器数。接下来的m 行，每行是一个实验的有关数据。第一个数赞助商同意支付该实验的费
用；接着是该实验需要用到的若干仪器的编号。最后一行的n个数是配置每个仪器的费用。
输出
第1 行是实验编号；第2
行是仪器编号；最后一行是净收益。
行是仪器编号；最后一行是净收益。
样例输入 复制
2 3
10 1 2
25 2 3
5 6 7样例输出 复制
1 2
1 2 3
17提示
由于答案不唯一，只输出原题目要求的第三行。