P15937 [TOPC 2021] ICPC Kingdom

ICPC 王国有 $n$ 座城市，编号为 $1$ 到 $n$，有 $m$ 条道路，编号为 $1$ 到 $m$，连接这些城市。每条道路连接两座城市，人们可以沿道路双向通行。城市 $i$ 有 $a_i$ 名居民。道路 $j$ 连接城市 $u_j$ 和 $v_j$，其经济效益为 $\left\lfloor \sqrt{a_{u_j} + a_{v_j}} \right\rfloor$。 一天，敌人入侵了 ICPC 王国，摧毁了所有道路。幸运的是，ICPC 军队击败了敌人并阻止了入侵。为了从战争中恢复，ICPC 国王雇佣了 $w$ 名工人来修复道路。每名工人最多可以修复一条道路，第 $i$ 名工人只能修复编号在 $b_1, b_2, \dots, b_{x_i}$ 中的一条道路。 现在国王希望修复道路以使王国恢复正常。考虑到成本，国王不希望修复计划中包含任何无用道路。如果一个修复计划包含无用道路，则存在一对城市 $p$ 和 $q$，使得从城市 $p$ 到城市 $q$ 存在多于一条简单路径。简单路径是指由互不相同的道路 $c_1, c_2, \dots, c_z$ 组成的序列，沿着 $c_1, c_2, \dots c_z$ 旅行恰好经过 $z+1$ 个不同的城市。 国王要求你计算在恰好修复 $k$ 条道路且不包含无用道路的情况下，能获得的最大经济效益。你需要对 $1$ 到 $n-1$ 之间的每个 $k$ 进行计算。

第一行包含 $n$ 和 $m$，以空格分隔。$n$ 是城市数量，$m$ 是道路数量。第二行包含 $n$ 个数字 $a_1, a_2, a_3 \dots a_n$，以空格分隔，分别表示城市 $1, 2, \dots, n$ 中的居民数量。接下来 $m$ 行，每行包含 $u_j$ 和 $v_j$，以空格分隔。道路 $j$ 连接城市 $u_j$ 和 $v_j$。接下来一行包含一个数字 $w$，表示工人的数量。接下来的 $w$ 行表示工人可以修复的道路。第 $(3 + i)$ 行包含若干以空格分隔的数字。第一个数字是 $x_i$，表示第 $i$ 名工人可以修复的道路数量。随后是该行中的 $x_i$ 个互不相同的整数 $b_1, b_2, \dots, b_{x_i}$。第 $i$ 名工人只能修复 $b_1, b_2, \dots, b_{x_i}$ 中的一条道路。

输出 $n-1$ 个数字。第 $i$ 个数字表示在修复计划恰好修复 $i$ 条道路且不包含无用道路时，能获得的最大经济效益；如果不存在这样的计划，则输出 $-1$。

- $1 \leq n \leq 100$ - $0 \leq m \leq 100$ - $1 \leq a_i \leq 10^9$ - $1 \leq u_i, v_i \leq n$，$u_i \neq v_i$ - $0 \leq w \leq 100$ 翻译由 DeepSeek V3.2 完成