P8240

KemononeRou · 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 需要一些卡常，目前最裂解。