boruvka 嘴巴杂记

如果 NOIP2024 考完后还有心思的话可能会写个最小生成树全家桶。

嘴巴概要

每次应对的局面都是若干个连通块，我们处理出每个连通块向外连出的最小边。然后每个连通块通过其最小边连出去合并。局面再次来到若干个连通块，重复操作至连通块数量为一。

一次局面后最坏情况下连通块个数至少减半，这里是 $O(\log)$ 的。每一次局面对于每个点（注意不是连通块）都要找到一个不连通点其中边权最小，即对于每个连通块找最小连出边。假设一次找点是 $O(1)$ 的，那么 $n$ 次就是 $O(n)$ 的。所以总时间复杂度 $O(n\log n)$。

前提是找最小连出边的时间复杂度是 $O(1)$ 的，不然时间复杂度就不能保证 $O(n\log n)$。

所以 boruvka 的应用主要是一些性质最小生成树题。这类题通常需要你抽象出最小生成树的模型，而通常这类题的边数极多。所以会卡 $O((n+m)\log m)$ 的 Prim 和 $O(m\log m)$ 的 Kruskal。

因此这种特殊性质最小生成树题也一般被称为菠萝题🍍。

题意：$n$ 个数 $a_1,\dots,a_n$，满足 $i<j$ 则可以连一条权值为 $a_j-a_i$ 的边，求最小生成树。（$n\leq 3\times 10^5$）

主要讲讲怎么 $O(1)$ 得每个连通块的最小连出边。

我们在 $O(n)$ 求每个点所属连通块的最小连出边时，同时维护一个最大值和次大值，这两个值不属于同一个连通块。每次更新最小连出边，如果最大值的所属连通块与当前点不同，就是 $col_x=\min{a_i-\text{mx}_1}$ 否则用次大值转移。

当然还要跑一次维护最小值和次小值的，因为上面是为了减数大，这里是为了被减数小，操作同理，不讲了。

因此这道题可以 $O(1)$ 得到每个连通块的最小连出边。又因为数据范围卡 Prim 和 Kruskal，所以这道题菠萝题实锤。