P16021 [ICPC 2021 NAC] The King' s Guards

在某个王国中，国王希望部署守卫来保护他的子民。他招募了若干名守卫，并为他们配备了重甲，以抵御强盗、外邦骑士以及其他不法之徒。他的守卫虽然勇猛，但遗憾的是他们并不聪明，会攻击任何穿着盔甲的人，甚至包括其他守卫！ 王国由若干村庄组成，村庄之间由道路相连。所有道路的质量都很差，有些泥泞不堪，有些桥梁摇摇欲坠。没有一条道路能承受身着全副盔甲的守卫通行。因此，国王必须决定修缮哪些道路，以便他的守卫能够抵达整个王国。道路是双向的。每名守卫只能被部署到王国中某个特定子集的村庄中。 国王需要在满足以下若干约束条件的前提下，最小化修缮道路的总成本： - 每名守卫都必须被部署，不能有守卫闲置。 - 每名守卫必须被部署到其允许部署的村庄子集内。 - 每个村庄必须恰好被一名守卫所覆盖（即可以到达）。如果有两名守卫能够互相到达，他们就会发生冲突。 请帮助国王确定在满足上述约束条件的前提下，修缮道路所需的最小总成本。

输入的第一行包含三个整数 $n$（$1 \le n \le 300$）、$r$（$0 \le r \le \frac{n(n-1)}{2}$）和 $g$（$1 \le g \le n$），其中 $n$ 是村庄的数量，$r$ 是道路的数量，$g$ 是守卫的数量。村庄的编号为 $1$ 到 $n$。 接下来的 $r$ 行，每行包含三个整数 $a$、$b$（$1 \le a < b \le n$）和 $c$（$1 \le c \le 1{,}000$）。每行描述一条连接村庄 $a$ 和村庄 $b$ 的道路，修缮该道路的成本为 $c$。这些道路是双向的，守卫可以从 $a$ 走到 $b$ 或从 $b$ 走到 $a$。每对村庄之间至多有一条道路。 接下来的 $g$ 行，每行首先有一个整数 $k$（$1 \le k \le n$），随后跟着 $k$ 个整数 $v$（$1 \le v \le n$）。每行描述某一名守卫可以被部署的村庄子集。不同守卫的子集之间可能有重叠。

输出一个整数，表示国王为了满足所有约束条件而需要修缮的道路的最小总成本。如果无法以任何方式部署守卫使得所有约束同时满足，则输出 $-1$。

翻译由 DeepSeek V3.2 完成