配点 : 200 点
問題文
n 项, 它们的编号最大为1 从 n 。
每件物品都有价值和重量,i 项的值为 v_i,重量为 w_i 。
您可以计算这些物品的总重量。 我想选择一些项目,以免超过 W 并最大化所选项目的总价值。
但是, 有m 条件。 第
j 个条件是 分别是 (a_j, b_j) 。 如果您选择 a_j 项目, 您必须选择 b_j 项目, 您必须选择b_j 项目, 您必须选择 a_j 项目。” 这就是它的意思。
满足所有这些条件后,n 物品的重量总和为 选择多项且不超过 W 时,求值之和的最大值。
制約
- 所有输入值都是整数。
- 1 \leq n \leq 100
- 0 \leq m \leq \frac {n(n-1)}{2}
- 1 \leq W \leq 10^4
- 1 \leq w_i \leq W
- 1 \leq v_i \leq 10^7
- 1 \leq a_i, b_i \leq n
- a_i \neq b_i
- i \neq j 然后, 满足所有(a_i, b_i) \neq (a_j, b_j) 和 满足 (a_i, b_i) \neq (b_j, a_j)
入力
输入是按以下格式从标准输入给出的。
n m W w_1 v_1 w_2 v_2 \vdots w_n v_n a_1 b_1 a_2 b_2 \vdots a_m b_m
出力
m 条件后, 选择多个项目时打印数值总和的最大值,以免超过n 物品的重量总和为 选择多项且不超过 W 。
入力例 1
3 1 10 3 2 5 4 3 3 1 2
出力例 1
6
1 第一项和 通过选择第 2 项,我们计算值的总和。 6 ,这是最佳的。
从条件来看, 请注意,您不能仅选择2 第一项和 通过选择第 3 项目。
入力例 2
4 0 10 1 1 2 2 3 3 4 4
出力例 2
10
您可以选择所有项目。
入力例 3
3 3 6 2 5 3 8 3 4 1 2 2 3 3 1
出力例 3
0
我无法选择任何项目。
入力例 4
1 0 10000 10000 10000000
出力例 4
10000000