You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

提示

感谢 @FlierKing 提供 spj

$1 \leq n, m \leq 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++;
}