boruvka 算法学习笔记

boruvka算法

就是最小生成树 B 算法。B 算法的思路是每次对每个连通块，求出它能连出去的权值最小的边，然后再按边权从小到大合并。由于每次操作连通块数至少减半，所以复杂度是 \(O(m\log n)\)。

1.CF1305G Kuroni and Antihype

题意：长为 \(n\) 的数列 \(a\)，现在要选择全部数，每一次你可以选择一个未被选择的数，也可以选择一个已经被选择了的数 \(a_i\)，再选择一个满足 \(a_i\&a_j=0\) 的未被选择的数 \(a_j\)，得到 \(a_i\) 的贡献，求选择所有数的贡献最大值。

思路：我们先加入点 \(n+1\) 权值为 0 来保证能选所有点，令 \(ans=-\sum a_i\)，然后将 \(a_i\&a_j=0\) 的点间连上 \(a_i+a_j\) 的边，然后求一个最大生成树即可。但是边数是 \(O(n^2)\) 量级的，我们考虑利用这道题的性质进行优化。我们设 \(f[S][2]\) 表示边权是 \(S\) 的二进制下子集的最大/次大边权，这个可以用 DP 求出，然后对于 \(a_i\)，根据 \(f[\complement a_i]\) 求出 \(i\) 所在集合能连出去的最大边权再加边即可。因此可以 \(O(w\log w)\) 拓展一轮，那么用上 B 算法就可以了。

复杂度 \(O(w\log n\log w)\)。

2.Tree MST

题意：有一棵树，现在用这棵树生成一张完全图，图上两点间的距离是 \(w_x+dis(x,y)+w_y\)，求最小生成树。

思路：考虑用 boruvka 算法。我们每次需要对于一个点，求出这个点连向不在一个联通块的点的最小边，可以用一次换根 DP 求出。

具体的，维护 \(w_x+dis_x\) 的最小值和不在一个联通块内的点的次小值就可以了。

复杂度 \(O(n\log n)\)。