Goblins And Gnomes 题解

思路

把每个大厅拆成二分图中的左点和右点，每条隧道 $u\to v$ 变成边 $u_Lv_R$。DAG 的最小点不相交路径覆盖数等于

$$p=n-\nu,$$

其中 $\nu$ 是二分图最大匹配。第 $i$ 波能够洗劫全部大厅，当且仅当 $p\le i$；因此必须保持 $n-\nu>i$。

封锁大厅 $u$ 的全部出边等价于删除 $u_L$，封锁全部入边等价于删除 $u_R$。

小规模直接枚举这 $2n$ 个删除动作的子集。对每个子集重算最大匹配，再做“波次、当前动作子集”的动态规划。上一波使用子集 $A$、当前波使用其超集 $B$ 时，准备时间为 $\lvert B\setminus A\rvert$。这样从原定义穷举所有永久封锁策略。

更大规模不必保留任意子集。设当前最大匹配为 $r>0$。当前二分图存在大小为 $r$ 的最小点覆盖；删除覆盖中的任意点后，剩余覆盖大小为 $r-1$，而删除一个点又不可能让最大匹配下降超过一，所以新最大匹配恰为 $r-1$。重复该过程可得到一个动作序列，使执行前 $j$ 个动作后的最大匹配恰为 $r-j$。

第二子任务每次扫描所有尚未删除的左右点，临时删除并重跑最大匹配，找到使匹配减一的动作。

满分算法在每次最大匹配后，从未匹配左点沿“未匹配边从左到右、匹配边从右到左”搜索。若可达点集合为 $Z$，Kőnig 定理给出的最小点覆盖是

$$(L\setminus Z)\cup(R\cap Z).$$

直接取其中一个点删除，不再逐候选试探。

最后只需决定每波前执行动作序列的多少个前缀。设初始匹配为 $r$，第 $i$ 波前至少要执行

$$need_i=\max(0,r+i-n+1)$$

个动作。令 $dp[i][j]$ 表示前 $i$ 波结束、累计执行前 $j$ 个动作时的最大得分，则

$$dp[i][j]=\max_{0\le h\le j}\left(dp[i-1][h]+\max(0,x_i-(j-h)y_i)\right),\qquad j\ge need_i.$$

记录前驱即可输出动作与波次零操作。

做法

满分程序先用 Kuhn 匹配得到初始 $r$。只要匹配非零，就从交错路搜索构造当前最小点覆盖，选择一个仍存在的左点或右点：左点输出正编号，右点输出负编号；从图中删除后重算匹配。得到长度 $r$ 的降匹配动作序列。

在这个序列上做 $O(kr^2)$ 的波次 DP，选择总分最大的末状态并逆推每波前的累计动作数。依次输出新增加的封锁动作，再输出一个 $0$ 召唤该波。

Testlib 检查器会独立重算每个输出前缀对应的最大匹配，验证每波都无法覆盖全部大厅，并把策略得分与标准答案的最优得分比较；因此允许任意不同的最优策略。

复杂度

子集枚举算法需要 $O(2^{2n}\cdot n^3+k3^{2n})$ 时间和 $O(k2^{2n})$ 空间。

逐候选试删算法使用朴素匹配时，时间复杂度为 $O(n^5+kn^2)$，空间复杂度为 $O(n^2)$。

最小点覆盖引导算法使用朴素 Kuhn 匹配时，时间复杂度为 $O(n^4+kn^2)$，空间复杂度为 $O(n^2)$。