P2762 太空飞行计划问题

    • 1.3K通过
    • 4.2K提交
  • 题目提供者 yyy2015c01 嘤嘤嘤
  • 评测方式 云端评测
  • 标签 网络流 网络流24题 O2优化 Special Judge
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    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个数是配置每个仪器的费用。

    输出格式:

    第1 行是实验编号;第2行是仪器编号;最后一行是净收益。

    输入输出样例

    输入样例#1: 复制
    2 3
    10 1 2
    25 2 3
    5 6 7
    输出样例#1: 复制
    1 2
    1 2 3
    17

    说明

    感谢@FlierKing 提供spj

    n,m<=50

    这道题数据是在windows生成的,输入数据中所有的换行都是'\r\n'而不是'\n'
    读入某实验需要用到的仪器编号的时候,可以这么读入。(感谢@zhouyonglong的提供)

    char tools[10000];
    memset(tools,0,sizeof tools);
    cin.getline(tools,10000);
    int ulen=0,tool;
    while (sscanf(tools+ulen,"%d",&tool)==1)//之前已经用scanf读完了赞助商同意支付该实验的费用
    {//tool是该实验所需仪器的其中一个      
        //这一行,你可以将读进来的编号进行储存、处理,如连边。
        if (tool==0) 
            ulen++;
        else {
            while (tool) {
                tool/=10;
                ulen++;
            }
        }
        ulen++;
    }
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。