题解：P14362 [CSP-S 2025] 道路修复 / road（暂无数据）

sheepchat · 2025-11-01 20:34:04 · 题解

唉，太失败了，204pts。

提供一个 O(n2^k\alpha(n+k)) 的做法。

给出一个结论：

如果一条边不在最小生成树上，那么加上若干条边后的最小生成树，这条边也不会出现。

回到本题，不妨枚举那些乡镇被城市化，问题变成一个最小生成树问题，已经有了个 O((n\alpha(n+k)+(m+nk)\log (m+nk)2^k) 做法。

显然无法通过，如果对于原图运用上面的结论，O(m) 边数会变成 O(n)，这是已经变成，再结合归并，我们得到 O(2^k(\alpha(n+k)n+(nk+m)\log k))，已经很优秀了，卡卡常该过。

但是，我们还能更加简化，不妨考虑把每个情况的考虑边数变成 O(n) 的具体地，我们还是沿用上述结论，不妨考虑扔掉一个乡镇，剩下的边集得到的最小生成树是被处理出来过的，这是在加上这个乡镇的话又多了若干条边，由于上述结论，只有剩下的边集得到的最小生成树和多出来的边是有用的，归并后跑最小生成树即可。