TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1937
  • 题目
  • P1937太空飞行计划
    限制 : 时间限制 : - MS   空间限制 : 65536 KB
    问题描述

           W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E={E1,E2,…,Em},和进行这些实验需要使用的全部仪器的集合I={I1,I2,…In}。实验Ej需要用到的仪器是I的子集Rj属于I。配置仪器Ik的费用为ck美元。实验Ej的赞助商已同意为该实验结果支付pj美元。
           W教授的任务是找出一个有效算法,确定在一次太飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。
          对于给定的实验和仪器配置情况,编程找出净收益最大的试验计划。
           输出最多能得到的净获利。

    输入格式

    第1行有2 个正整数m和n。m是实验数,n是仪器数。(n,m<=50)
    接下来的m 行,每行是一个实验的有关数据。第一个数赞助商同意支付该实验的费用;接着是该实验需要用到的若干仪器的编号。
    最后一行的n个数是配置每个仪器的费用。

    输出格式

    一行,包含一个整数,表示最大净收益

    样例输入 1

    2 3
    10 1 2
    25 2 3
    5 6 7

    样例输出 1

    17

    样例输入 2

    6 22
    9 2 7
    4 5 6 7 9
    3 2
    10 2
    10 3 6 11
    8 4 5 6 9
    6 1 3 7 10 2 5 8 3 5 7 6 10 6 6 2 4 6 5 5 3 9

    样例输出 2

    16

    提示

    样例1说明,做了1,2两个实验,用到的仪器是1,2,3
    样例2说明,做了1,3,4三个实验,用到的仪器是2和7


    来源  感谢 Wo_ai_WangYuan 修改题目并放上数据