自动搬运

查看原文

来自洛谷，原作者为

	I_am_AKed_by_NOI 数学里有一个虐心的事实：两条平行线永不相交。两条相交的线，先是不停相近，但在经历唯一的相交后，越离越远。

搬运于2025-08-24 21:39:51，当前版本为作者最后更新于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}$ 减少很多，可以通过。