题目名称	727. [网络流24题] 太空飞行计划
输入输出	`shuttle.in/out`
难度等级	★★★
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	Makazeu 于2012-04-04加入
开放分组	全部用户
提交状态
分类标签	图论网络流
	分享题解

通过：336，提交：1203，通过率：27.93%
confoo	100	0.000 s	0.00 MiB	C++
Rapiz	100	0.000 s	0.00 MiB	C++
AAAAAAAAAA	100	0.000 s	0.00 MiB	C++
WildRage	100	0.000 s	0.00 MiB	C++
小金	100	0.000 s	0.00 MiB	C++
Void	100	0.000 s	0.57 MiB	C++
Void	100	0.001 s	0.57 MiB	C++
hnust_xiaochaoqu	100	0.002 s	0.31 MiB	C++
Soviets	100	0.002 s	0.38 MiB	C++
lalalala	100	0.002 s	0.42 MiB	C++

关于太空飞行计划的近10条评论(全部评论)
为什么我不判‘\r’也没事。。。 CSU_Turkey 2017-12-29 15:44 27楼
智障了我，为了输出前两行而改了一个小时，才想起来根据贪心思想只有最后一遍阻塞增广的会在答案里。。 UPD:这个结论应该是不对的，但是在这道题和数据里是没问题的。 _Itachi 2017-12-23 11:35 26楼
换行符居然是'\r',被坑惨了，一直是T，吓得我查了好几遍freopen。。。还好看了评论。。。雨季 2017-11-13 16:55 25楼
我的dinic多路增广写炸了。。。。 TLE了八个点。。 HeHe 2017-06-28 16:21 24楼
神奇建图 kZime 2017-06-25 13:46 23楼
这题有SPJ嘛？ wumingshi 2017-03-15 14:59 22楼
读入用/r 多亏看了评论。祖国栋梁 2017-03-13 19:27 21楼
读入真烦 Rapiz 2017-03-04 16:27 20楼
为什么网络流题目要输出方案…… cstdio 2017-01-31 21:50 19楼
人蠢，被读入卡了一万次O Q. 比如getline（）读的第一个字符是空格，比如“\r”卡getline（），比如getchar（）结束条件判错等等等等，总之感谢@chenyao233 的提示 Mealy 2017-01-31 21:03 18楼

727. [网络流24题] 太空飞行计划

★★★ 输入文件：shuttle.in 输出文件：shuttle.out 简单对比
时间限制：1 s 内存限制：128 MiB

【问题描述】

W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E={E₁,E₂,…,E_m}，和进行这些实验需要使用的全部仪器的集合I={ I₁, I₂,…,I_n}。实验Ej 需要用到的仪器是I的子集R_j∈I。配置仪器I_k的费用为c_k美元。实验E_j的赞助商已同意为该实验结果支付p_j美元。W教授的任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。

【编程任务】

对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划。

【数据输入】

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

【结果输出】

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

【输入文件示例】shuttle.in

【输出文件示例】shuttle.out

1 2
1 2 3
17