题解 P3366 【【模板】最小生成树】

· · 题解

貌似还没见到 Borůvka (Sollin) 算法求最小生成树?

这个算法的教程在网上极少…… 翻了好多的博客都没理解,最终找到了维基百科的 Borůvka's algorithm 词条,终于弄懂了这个十分古老的算法。

Borůvka 其实是一种多路增广的 prim。Prim 算法由一个点开始,往外不断贪心地找最短边,然后不断扩大连通块,直到形成一棵树。而 Borůvka 算法每一次的增广,会对现在的每一个连通块都找一遍的最短边,最后每个连通块择优,将这些边全部连上。

算法的执行流程大约是这样的:

利用维基百科的样例可以形象地说明如上步骤:

这样,每一次合并的 O(M) 的,但是每一次合并后,连通块的个数都减少一半。这样一来,只要 \log N 次,就能合并成最小生成树了。所以总时间复杂度是 O(M \log N) 的。Borůvka 的优势也正在此,它只需要 \log N 次的合并,这是另外两个 MST 算法所难以达到的。因此,一旦有题目想考察 Borůvka 算法,一定跟这个特性密切相关。

代码:

#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;
}