P2632 Explorer 题解

I_am_AKed_by_NOI · 2023-08-21 11:41:13 · 题解

题目大意

给定两条直线，其中一条上有 n 个点，另一条上有 m 个点，求这 n+m 个点的最小生成树。

题目思路

假设我们把这 n+m 个点两两连线，就会形成一个非常非常稠密的图，一共有 \frac{(n+m)^2}{2} 条边，显然是不可取的。

事实上，我们可以减少一下不必要的边。

• 同一条直线上，只需要连接相邻的连个点即可。

证明：

这个还是比较显然的。

如果 a_1,a_2,a_3 从左到右在同一条直线上，那么 a_1 与 a_3 就不必相连，因为 a_3 肯定会与 a_2 相连，那么连接 a_1,a_3 的代价相当于连接 a_1,a_2 再连接 a_2,a_3，前者只联通了 a_1,a_3 两个点，而后者联通了 a_1,a_2,a_3 三个点，显然后者比前者更优。所以在同一条直线上，只需要连接相邻的连个点即可。

• 若一个点要另一条直线所在的点，则只需连接有这点向另一条直线做垂线得到的垂足旁边的两个点

证明：

垂线段最短，所以这垂足旁两个点到这个点的距离最短。设该点为 x，垂足旁的两个点为 a_1,a_2（假设 a_1 离 x 更近），与它们在同一直线上的任意一点为 a_3。

这里默认 a_1,a_2,a_3 从左到右，其他情况与此情况类似。

要让他们联通，连接 x,a_1 和 a_1,a_2 与 a_2,a_3 显然是最优的，所以 x 不会与 a_3 连接，那么结论得证。

这样子边数就从 \frac{(n+m)^2}{2} 减少很多，可以通过。