前言

例题：AizuOJ ALDS_12A & AizuOJ GRL_2_A

本题可以使用普里姆(Prim)算法或克鲁斯卡尔(Kruskal)算法进行实现。

两种算法的简单比较：

时间复杂度 最适合
Prim O(n^2) 稠密图
Kruskal O(E * log E)，E为边数 稀疏图

视频：最小生成树(Kruskal(克鲁斯卡尔)和Prim(普里姆))算法动画演示

以下代码是 AizuOJ GRL_2_A 的解法。

普里姆算法

代码如下：

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cstdio>
#include <vector>
#include <limits.h>

using namespace std;

#define MAX 10000

typedef pair<int, int> PII;

vector<PII> D[MAX]; 	//PII(id, w)
int sum = 0, d[MAX];
//int p[MAX];
bool seen[MAX] = {false};

int main() {
	int V, E, s, t, w;

	scanf("%d %d", &V, &E);

	for (int i = 0; i < V; i++) {
		d[i] = INT_MAX;
	}

	for (int i = 0; i < E; i++) {
		scanf("%d %d %d", &s, &t, &w);
		D[s].push_back(PII(t, w));
		D[t].push_back(PII(s, w));
	}

	int ct = 0;
	s = 0;
	seen[0] = true;

	while (ct < V - 1) {
		for (int i = 0; i < D[s].size(); i++) {
			t = D[s][i].first;
			w = D[s][i].second;
			if (!seen[t] && d[t] > w) {
				d[t] = w;
//				p[t] = u;
			}
		}

		int min = 0;
		for (int i = 0; i < V; i++)
			if (!seen[i] && d[i] < d[min])
				min = i;

		seen[min] = true;
		s = min;
		sum += d[min];
		ct++;
	}

	printf("%d\n", sum);

	return 0;
}

运行结果：

Lang Status Judge Time Memory Code
C++ AC 20/20 00.22s 6024KB 861B

克鲁斯卡尔算法

代码如下：

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <limits.h>

using namespace std;

#define MAX 10000

typedef struct {
	int v1, v2, w;
} Info;

vector<Info> D;
int p[MAX], h[MAX], d[MAX];

bool cmp(const Info a, const Info b) {
	return a.w < b.w;
}

int find(int a) {
	if (p[a] != a) {
		p[a] = find(p[a]);
	}
	return p[a];
}

void unite(int x, int y) {
	int rX = find(x);
	int rY = find(y);

	if (rX != rY) {
		if (h[rX] > h[rY])
			p[rY] = rX;
		else {
			p[rX] = rY;
			if (h[rX] == h[rY])
				h[rY]++;
		}
	}
}


int main() {
	int V, E, sum = 0;
	int s, t, w;

	scanf("%d %d", &V, &E);

	for (int i = 0; i < V; i++) {
		d[i] = INT_MAX;
		p[i] = i;
		h[i] = 0;
	}

	for (int i = 0; i < E; i++) {
		scanf("%d %d %d", &s, &t, &w);
		Info tmp = {s, t, w};
		D.push_back(tmp);
	}

	sort(D.begin(), D.end(), cmp);

	for (int i = 0; i < E; i++) {
		if (find(D[i].v1) != find(D[i].v2)) {
			unite(D[i].v1, D[i].v2);
			sum += D[i].w;
		}
	}

	printf("%d\n", sum);

	return 0;
}

运行结果：

Lang Status Judge Time Memory Code
C++ AC 20/20 00.02s 4696KB 1013B