CHDOJ
首页
题库
题单
比赛
评测
用户
讨论
帮助
工具
云剪贴板
树图画板
代码对比
登录
注册
4072: 太空飞行计划
时间限制:1000 ms
内存限制:256 MB
Special Judge
上传者:
提交:1
通过:1
提交
提交记录
讨论
统计
题目描述
W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合 $ E = \{ E_1, E_2, \cdots, E_m \} $,和进行这些实验需要使用的全部仪器的集合 $ I = \{ I_1, I_2, \cdots, I_n \} $。实验 $ E_j $ 需要用到的仪器是 $ I $ 的子集 $ R_j \subseteq I $。
配置仪器 $ I_k $ 的费用为 $ c_k $ 美元。实验 $ E_j $ 的赞助商已同意为该实验结果支付 $ p_j $ 美元。W 教授的任务是找出一个有效算法,确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。
对于给定的实验和仪器配置情况,编程找出净收益最大的试验计划。
输入格式
第 $ 1 $ 行有 $ 2 $ 个正整数 $ 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
数据范围与提示
分类标签
图论
网络流24题
网络流