AT_kupc2019_b.ナップサック問題

有 $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$，并输出所能获得的最大总价值。

输入通过标准输入按以下格式给出。

$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 \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)$

样例解释 1

可以选择第 $1$ 个和第 $2$ 个物品，使得总价值为 $6$，这是最优解。请注意，由于条件限制，不能只选择第 $2$ 个和第 $3$ 个物品。

样例解释 2

可以选择所有物品。

样例解释 3

无法选择任何物品。

由 ChatGPT 4.1 翻译