题解 P3366 【【模板】最小生成树】
Tweetuzki
2018-11-05 23:01:01
貌似还没见到 Borůvka (Sollin) 算法求最小生成树？
这个算法的教程在网上极少…… 翻了好多的博客都没理解，最终找到了维基百科的 [Borůvka's algorithm](https://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm) 词条，终于弄懂了这个十分古老的算法。
Borůvka 其实是一种多路增广的 prim。Prim 算法由一个点开始，往外不断贪心地找最短边，然后不断扩大连通块，直到形成一棵树。而 Borůvka 算法每一次的增广，会对现在的每一个连通块都找一遍的最短边，最后每个连通块择优，将这些边全部连上。
算法的执行流程大约是这样的：
- 对于现在的每个连通块，找到从这个连通块出发，不在最小生成树中的、到达别的连通块的最短边。（特别注意：若权值相同，则需要再按照另一个维度严格排序，常用标号大小排序。即边权相同时，认为编号小的边短。这样处理是为了避免两个连通块互相连的时候出现环）
- 全部找完后，将这些边加入最小生成树中。（可能出现两个连通块互连的情况，那么这时在第一个连通块连完这条边后，标记一下，说明该边已被加入最小生成树，下一次弹掉即可）
利用维基百科的样例可以形象地说明如上步骤：
这样，每一次合并的 $O(M)$ 的，但是每一次合并后，连通块的个数都减少一半。这样一来，只要 $\log N$ 次，就能合并成最小生成树了。所以总时间复杂度是 $O(M \log N)$ 的。Borůvka 的优势也正在此，它只需要 $\log N$ 次的合并，这是另外两个 MST 算法所难以达到的。因此，一旦有[题目](https://codeforces.com/problemset/problem/888/G)想考察 Borůvka 算法，一定跟这个特性密切相关。
代码：
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MaxN = 5000 + 5, MaxM = 200000 + 5;
int N, M;
int U[MaxM], V[MaxM], W[MaxM];
bool used[MaxM];
int par[MaxN], Best[MaxN];
void init() {
scanf("%d %d", &N, &M);
for (int i = 1; i <= M; ++i)
scanf("%d %d %d", &U[i], &V[i], &W[i]);
}
void init_dsu() {
for (int i = 1; i <= N; ++i)
par[i] = i;
}
int get_par(int x) {
if (x == par[x]) return x;
else return par[x] = get_par(par[x]);
}
inline bool Better(int x, int y) {
if (y == 0) return true;
if (W[x] != W[y]) return W[x] < W[y];
return x < y;
}
void Boruvka() {
init_dsu();
int merged = 0, sum = 0;
bool update = true;
while (update) {
update = false;
memset(Best, 0, sizeof Best);
for (int i = 1; i <= M; ++i) {
if (used[i] == true) continue;
int p = get_par(U[i]), q = get_par(V[i]);
if (p == q) continue;
if (Better(i, Best[p]) == true) Best[p] = i;
if (Better(i, Best[q]) == true) Best[q] = i;
}
for (int i = 1; i <= N; ++i)
if (Best[i] != 0 && used[Best[i]] == false) {
update = true;
merged++; sum += W[Best[i]];
used[Best[i]] = true;
par[get_par(U[Best[i]])] = get_par(V[Best[i]]);
}
}
if (merged == N - 1) printf("%d\n", sum);
else puts("orz");
}
int main() {
init();
Boruvka();
return 0;
}
```