最小生成树_解题技巧

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 424 阅读时长 ≈ 1 分钟

模板

Kruskal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e3 + 50, maxm = 2e5 + 50;
int n, m, ans, cnt, fa[maxn];

struct node {
  int x_, y_, z_;
  bool operator<(const node &a) const { return z_ < a.z_; }
} e[maxm];

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

void kruskal() {
  sort(e + 1, e + 1 + m);
  for (int x, y, i = 1; i <= m; ++i) {
    x = find(e[i].x_), y = find(e[i].y_);
    if (x != y) {
      ++cnt, ans += e[i].z_, fa[x] = y;
    }
  }
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) fa[i] = i;
  for (int x, y, z, i = 1; i <= m; ++i) {
    cin >> x >> y >> z;
    e[i] = {x, y, z};
  }
  kruskal();
  // 若连通，最小生成树只有n-1条边
  if (cnt == n - 1)
    cout << ans << endl;
  else
    cout << "orz" << endl;
  return 0;
}

Prim

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e3 + 50, maxm = 2e5 + 50;
int n, m, ans, cnt, a[maxn][maxn], d[maxn], v[maxn];

void prim() {
  d[1] = 0;
  for (int i = 1; i < n; ++i) {
    int x = 0;
    for (int j = 1; j <= n; ++j) {
      if (!v[j] && (x == 0 || d[j] < d[x])) x = j;
    }
    v[x] = 1;
    for (int y = 1; y <= n; ++y) {
      if (!v[y] && d[y] > a[x][y]) {
        d[y] = a[x][y];
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    if (d[i] == 0x3f3f3f3f) {
      cout << "orz" << endl;
      return;
    }
    ans += d[i];
  }
  cout << ans << endl;
}

int main() {
  cin >> n >> m;
  memset(a, 0x3f, sizeof(a)), memset(d, 0x3f, sizeof(d));
  for (int x, y, z, i = 1; i <= m; ++i) {
    cin >> x >> y >> z;
    a[x][y] = a[y][x] = min(a[x][y], z);
  }
  prim();
  return 0;
}

核心

以最小的代价，让集合内部连通

Kruskal更倾向以集合的方式建模，Prim则更方便地记录最小生成树

练习题