自动搬运

查看原文

来自洛谷，原作者为

	KemononeRou 僕は 僕は まだ旅の途中

搬运于2025-08-24 22:37:13，当前版本为作者最后更新于2022-04-04 23:44:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

三种做法，看个乐子。

一个很显然的想法就是求出每个点到最近的守卫的距离，可以将每个守卫都当作一个起点，一起丢到队列里跑 dijkstra 解决。

一条边的边权是两边的点的最短路的最小值。

我们要求的相当于就是从 $S$ 到 $T$ 所有路径中最小边权的最大值。

第一种做法

我们要使得走过的边权最小值尽量大，那么一些边权较小的边是不会被走过的。

于是我们就能想到构建一颗最大生成树，这样就能保证每个点的连通情况不变的前提下，各个点之间的边权最小值最大。

于是就变成了查询树上两点之间的边权最小值，这里用的倍增解决。

复杂度 $O(m\log{m})$。

Code，目前最优解。

第二种做法

脑抽了觉得第一种做法不对，就想到了这种做法。

考虑将询问离线，然后按边权从大到小加边，然后合并两个连通块。

每个连通块需要维护一个点在这个集合中，而另一个点不在这个集合中的询问编号。

考虑启发式合并，用 set 维护询问编号。

合并前遍历小的集合，在大的集合中查询是否存在相同的询问，询问的答案就是当前加入的这条边的边权。

合并时将小的集合向大的集合合并，并将得到答案的询问移除。

复杂度 $O(n\log^2{Q})$。

Code，跑得比较快。

第三种做法

第二种做法写挂了，以为又假了，就想到了这种做法。

考虑将询问离线，然后还是按边权从大到小加边。

一个神秘思路就是每次加了边之后枚举每个询问，判断是否加边前不连通但是加边后联通，询问的答案即为当前边的边权。

发现这个是每操作一次就判断 $Q$ 次，复杂度是 $O(mQ)$ 的。

考虑将操作分块，块大小为 $S$。

每操作 $S$ 次后，求出操作 $S$ 次前不连通但是操作后连通的询问有哪些。

然后将这些询问拿出来，重新跑这 $S$ 次操作，每做一次操作判断一次是否连通。

考虑到每个询问都会跑 $S$ 次操作，找操作后连通的询问一共要跑 $\dfrac{m}{S}$ 次，所以复杂度是 $O(QS\alpha(n)+\dfrac{mQ}{S})$。

取 $S=\sqrt{m}$ 可过。

Code，不开 O2 需要一些卡常，目前最裂解。