题解：CF1419F Rain of Fire

Abczzzzz · 2026-04-25 15:32:53 · 题解

没有那个点就是最小生成树板子。加了一个点之后你的距离就不好处理了，因为暴力枚举加点需要三次方。考虑转换思路，从二分后判连通性入手。这个时候你就可以枚举平方了。分讨一下：

• 一个连通块，直接返回1。
• 两个连通块，枚举两个点即可。
• 三个连通块，感性理解一下一定有两个点在同一坐标，再感性理解一下这两个点在这个坐标上不是相邻的话一定不优，所以枚举相邻两点即可。
• 四个连通块，如上枚举两边即可。