CF1525F Goblins And Gnomes

Monocarp 玩一款名为 “Goblins and Gnomes” 的电脑游戏。在这款游戏中，他管理着一个大型的地精地下城市，并需要防御成群的哥布林的进攻。 城市由 $n$ 个大厅和 $m$ 条单向隧道组成。这些隧道有如下性质：如果一个哥布林离开了某个大厅，他就无法再回到该大厅。 城市将会遭受 $k$ 波哥布林的进攻；在第 $i$ 波进攻中，会有 $i$ 个哥布林攻击城市。Monocarp 的目标是抵御全部 $k$ 波进攻。 第 $i$ 波进攻的过程如下：首先，有 $i$ 个哥布林出现在城市的某些大厅并对其进行掠夺；每个大厅最多只会出现一个哥布林。然后，哥布林们会沿着隧道移动，掠夺他们经过的所有大厅。 哥布林非常贪婪且狡猾，他们会选择各自的路径，使得没有两个哥布林经过同一个大厅。在所有可能的进攻方案中，他们会选择能够掠夺最多大厅的方案。哥布林掠夺完毕后会离开城市。 如果在某一波进攻中所有大厅都被掠夺——Monocarp 就会输掉游戏。否则，城市会被修复。如果某个大厅在某一波被掠夺，哥布林在后续的波次中仍然会对其感兴趣。 在每一波进攻前，Monocarp 可以花时间进行准备。Monocarp 对于准备时间没有严格限制（他可以自行决定何时召唤每一波），但准备时间越长，通过该波获得的分数就越少。如果 Monocarp 为第 $i$ 波准备了 $t_i$ 分钟，那么通过该波他将获得 $\max(0, x_i - t_i \cdot y_i)$ 分（显然，如果他没有输掉的话）。 在准备期间，Monocarp 可以封锁隧道。他可以花费一分钟来封锁某个大厅所有出发的隧道，或者封锁所有通往某个大厅的隧道。如果 Monocarp 在准备期间封锁了某条隧道，那么在后续的所有波次中该隧道都保持封锁。 请帮助 Monocarp 抵御所有 $k$ 波哥布林的进攻，并获得尽可能多的分数！

第一行包含三个整数 $n$、$m$ 和 $k$（$2 \le n \le 50$，$0 \le m \le \frac{n(n - 1)}{2}$，$1 \le k \le n-1$），分别表示城市中的大厅数、隧道数和哥布林进攻的波数。 接下来的 $m$ 行描述隧道。第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$），表示有一条从大厅 $u_i$ 到大厅 $v_i$ 的隧道。隧道结构满足：如果哥布林离开某个大厅，就无法再回到该大厅。任意一对大厅之间最多只有一条隧道。 接下来的 $k$ 行描述得分系统。第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i \le 10^9$，$1 \le y_i \le 10^9$）。如果 Monocarp 为第 $i$ 波准备了 $t_i$ 分钟，则通过该波他将获得 $\max(0, x_i - t_i \cdot y_i)$ 分。

请输出 Monocarp 的最优策略，格式如下： 首先输出一个整数 $a$（$k \le a \le 2n + k$），表示 Monocarp 总共执行的操作数。接下来按顺序输出每个操作。第 $i$ 个操作用一个整数 $b_i$（$-n \le b_i \le n$）描述，具体如下： - 如果 $b_i > 0$，表示 Monocarp 封锁所有从大厅 $b_i$ 出发的隧道； - 如果 $b_i < 0$，表示 Monocarp 封锁所有通往大厅 $|b_i|$ 的隧道； - 如果 $b_i = 0$，表示 Monocarp 召唤下一波哥布林进攻。 同一个封锁操作 $b_i$ 不能重复执行。Monocarp 必须在召唤的所有波次中存活（即哥布林不能掠夺所有大厅）。Monocarp 必须恰好召唤 $k$ 波进攻，并且获得尽可能多的总分。 如果存在多种最优策略，输出任意一种即可。

在第一个样例中，Monocarp 首先封锁所有通往大厅 $2$ 的隧道，然后封锁所有通往大厅 $3$ 的隧道，之后依次召唤所有波次。他为第 $1$ 波准备了两分钟，因此获得 $98$ 分。之后没有再准备，因此每一波都获得最大分数（$200$、$10$ 和 $100$）。总共获得 $408$ 分。 在第二个样例中，Monocarp 立即召唤第一波并获得 $100$ 分。在第二波前，他封锁所有通往大厅 $3$ 的隧道，花费一分钟准备，因此获得 $195$ 分。第三波没有准备，获得 $10$ 分。第四波前，他封锁所有从大厅 $1$ 出发的隧道，花费一分钟，因此获得 $99$ 分。总共获得 $404$ 分。 在第三个样例中，无论 Monocarp 为波次准备多少分钟，都无法获得分数。因此他选择封锁城市中所有隧道，花费 $5$ 分钟。虽然没有得分，但他成功存活下来。 由 ChatGPT 4.1 翻译