最小生成树
# 概念
找到权值最小的树，使得图连通
# 思路
# Kruskal 算法
贪心思想，将边权重从小到大排序，每次选择最小的边，如果边上两个顶点在同一个集合中，那么会出现环，所以跳过
# Prim 算法
贪心思想，将点分成未访问和已经访问，找到未访问的点到已经访问的点中的最短边，直到所有点都访问过
# 题目
# HDU 1233
http://acm.hdu.edu.cn/status.php?user=dyxinhun&pid=1233&status=5
# Kruskal
//
// Created by Administrator on 2021/10/29.
//
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 101;
int f[N];
class Edge{
public:
int a, b, c;
Edge(int a, int b, int c):a(a), b(b), c(c){}
};
vector<Edge> E;
void init(){
for(int i = 0; i < N; i++) f[i] = i;
E.clear();
}
// 并查集路径压缩
int find(int x){
return f[x] == x ? x : find(f[x]);
}
// 如果边的两个端点不在同一个集合，那么添加到结果中，并且合并这两个点
void kruskal(){
int res = 0;
for(Edge t: E){
int a = t.a, b = t.b, c = t.c;
if(find(a) != find(b)){
res += c;
f[find(a)] = find(b);
}
}
printf("%d\n", res);
}
int main(){
int n;
while(scanf("%d", &n) && n){
init();
int a, b, c;
for(int i = 0; i < n*(n-1)/2; i++){
scanf("%d %d %d", &a, &b, &c);
E.push_back(Edge(a, b, c));
}
sort(E.begin(), E.end(), [](Edge &x, Edge &y){
return x.c < y.c;
});
kruskal();
}
return 0;
}
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
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
# Prim
写法和 迪杰斯特拉非常相似，只是在更新的时候的不同
//
// Created by Administrator on 2021/10/29.
//
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 101;
int m[N][N]; // 邻接矩阵
bool used[N];
int d[N];
void init(){
memset(m, 0x3f, sizeof(m));
for(int i = 0; i < N; i++) m[i][i] = 0;
memset(used, 0, sizeof(used));
memset(d, 0x3f, sizeof(d));
}
void prim(int n){
int res = 0;
for(int i = 1; i <= n; i++) d[i] = m[1][i];
used[1] = true;
for(int i = 0; i < n-1; i++){ // 这层循环是控制要找几条边，点有n个，那么边的数量一定是 n-1
int minv = (int)0x3f3f3f3f, minj = -1;
for(int j = 1; j <= n; j++){
if(!used[j] && d[j] < minv){
minv = d[j];
minj = j;
}
}
used[minj] = true;
res += minv;
// 更新该点到其他所有点的距离
for(int k = 1; k <= n; k++){
if(!used[k] && m[minj][k] < d[k]){
d[k] = m[minj][k];
}
}
}
printf("%d\n", res);
}
int main(){
int n;
while(scanf("%d", &n) && n){
init();
int a, b, c;
for(int i = 0; i < n*(n-1)/2; i++){
scanf("%d %d %d", &a, &b, &c);
m[a][b] = m[b][a] = c;
}
prim(n);
}
return 0;
}
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
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
# 参考链接
编辑 (opens new window)
上次更新: 2025/05/21, 06:42:57