#P6001. 「网络流 24 题」太空飞行计划

    ID: 125 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>Special Judge网络流最小割最大权闭合子图网络流 24 题

「网络流 24 题」太空飞行计划

题目描述

W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合 E={E1,E2,,Em} E = \{ E_1, E_2, \cdots, E_m \} ,和进行这些实验需要使用的全部仪器的集合 I={I1,I2,,In} I = \{ I_1, I_2, \cdots, I_n \} 。实验 Ej E_j 需要用到的仪器是 I I 的子集 RjI R_j \subseteq I

配置仪器 Ik I_k 的费用为 ck c_k 美元。实验 Ej E_j 的赞助商已同意为该实验结果支付 pj p_j 美元。W 教授的任务是找出一个有效算法,确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。

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

输入格式

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

输出格式

1 1 行是实验编号,第 2 2 行是仪器编号,数字之间用一个空格隔开。最后一行是净收益。

2 3
10 1 2
25 2 3
5 6 7
1 2
1 2 3
17

数据范围与提示

1n,m50 1 \leq n, m \leq 50