Boruvka 算法学习笔记

介绍

Boruvka 算法相当于多源的 Prim。我们维护若干个块。

刚开始

T

中没有边，每个点都是一个块。

在每轮算法中：

找到每个块的最小边（最小的向外连的边）。
一次尝试连接每个最小边。

算法进行

O(\log n)

轮。

算法的具体复杂度取决于求最小边的方式，这是根据题目而定的。对于模板题，一种简单的方式是

O(m)

地扫描每个边。

这个并查集过程又很像 Kruskal，但 Boruvka 不需要排序。

CPP

#include <bits/stdc++.h>
#define int long long
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define _rep(i, l, r) for (int i = (l); i >= (r); i--)

using namespace std;

constexpr int N = 5010, M = 2e5 + 10;

struct Edge {
  int u, v, w;
} e[M];
int n, m;
int mn[N];

int fa[N], rk[N];

void init() {
  rep (i, 1, n) fa[i] = i;
}

int find(int x) {
  if (x == fa[x]) return x;
  return fa[x] = find(fa[x]);
}

bool merge(int x, int y) {
  int fx = find(x), fy = find(y);
  if (fx == fy) return 0;
  if (rk[fx] < rk[fy]) fa[fx] = fy;
  else if (rk[fx] > rk[fy]) fa[fy] = fx;
  else fa[fy] = fx, rk[fx]++;
  return 1;
}

int Boruvka() {
  init();
  int res = 0;
  for (;;) {
    memset(mn, 0, sizeof(mn));
    rep (i, 1, m) {
      int u = e[i].u, v = e[i].v, w = e[i].w;
      int fu = find(u), fv = find(v);
      if (fu == fv) continue;
      if (!mn[fu] || e[mn[fu]].w > w) mn[fu] = i;
      if (!mn[fv] || e[mn[fv]].w > w) mn[fv] = i;
    }
    bool flag = 0;
    rep (i, 1, n) {
      if (fa[i] != i || mn[i] == 0) continue;
      flag = 1;
      int u = e[mn[i]].u, v = e[mn[i]].v, w = e[mn[i]].w;
      if (merge(u, v)) res += w;
    }
    if (!flag) break;
  }
  return res;
}

signed main() {
  cin >> n >> m;
  rep (i, 1, m) {
    int u, v, w;
    cin >> u >> v >> w;
    e[i] = {u, v, w};
  }

  int cnt = 0, res = Boruvka();
  rep (i, 1, n) cnt += find(i) == i;
  if (cnt == 1) cout << res;
  else cout << "orz";

  return 0;
}

Boruvka 算法学习笔记

文章操作

介绍

相关推荐

评论

Boruvka 算法学习笔记