CF2041N Railway Construction 题解

一个性质都没想到，还卡常卡了半天结果找个 AI 帮我卡了下直接进两秒了，感觉要被 AI 替代了。

为了方便，我们把点按照点权从小到大重标号一下，接下来默认点权单调不减。

先不考虑删点。

考虑没有这 $m$ 条禁用边的情况，此时显然把所有点都连到 $1$ 号点上就是 MST。

那么有了这 $m$ 条禁用边，我们可以把每个点连到最小的没有被禁用的点上，去一下重边，这样肯定是最优的，但是这样连完图不一定是连通的。不过，这个图有一个性质：

证明：假设有 $k$ 个连通块，那么这些连通块中点权最小的点，两两之间不能有边，所以 $m=O(k^2)$，$k=O(\sqrt{m})$。

于是，我们再在这个图上跑不带堆优化的 $O(|V|^2+|E|)$ 的 prim 算法，就能得到在这种带有特殊性质的图下，一种 $O(n+m)$ 的求最小生成树的方式。

这其中可能有一个问题，就是两个连通块之间的最小边权如何计算的问题。设连通块 $p,q$ 之间的边数为 $m_{p,q}$，那么我们找出连通块 $p$ 中点权最小的 $m_{p,q}+1$ 个点，并到 $q$ 中找到它们分别能连的最小点即可。这样对于两个连通块复杂度是 $O(m_{p,q})$ 的，总复杂度就是 $\sum O(m_{p,q})=O(m)$ 的。

接着考虑删点怎么做，比较自然的，我们先求出原图的 MST，然后在这基础上考虑。有这样一个性质：

证明：点 $i$ 要成为非叶子节点，就需要有点 $p$ 不能连向点 $1\sim i-1$，那么就需要 $O(i)$ 条禁用边，而这些点编号不同，编号总和为 $O(m)$，有自然根号点数为 $O(\sqrt{m})$。

那么对于叶子节点显然我们可以 $O(1)$ 求出答案，而对于 $O(\sqrt{m})$ 个非叶子节点，直接对每个都重跑一遍 $O(n+m)$ 求 MST 即可，时间复杂度就是 $O(n\sqrt{m}+m\sqrt{m})$ 的，足以通过。

对于无解的判断有不少细节，如果原图求不出 MST，先特判以下 $n=2$ 的情况，此时输出两个 $0$。否则如果有一个点对其它所有点的边都被禁用了，那么就对这个点跑一遍 MST，其它的全输出 $-1$ 即可。否则如果没有这样的点但还是求不出 MST 的话，说明无论删哪个点，原图都能分成两个中间没有边的连通块，全输出 $-1$ 即可。

代码写的比较烂，但还是放一下吧：submission