洛谷 P1195.口袋的天空

题目链接：https://www.luogu.com.cn/problem/P1195

今天上算法设计课，复习一下 Kruskal 和并查集。

放AC代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n, m, k, ans;
 4 int p[1010];
 5 
 6 struct node
 7 {
 8     int u, v, w;
 9 }edge[10010];
10 
11 int cmp(node a, node b)
12 {
13     return a.w < b.w;
14 }
15 
16 int getParent(int o)
17 {
18     return o == p[o] ? o : getParent(p[o]);
19 }
20 
21 int main()
22 {
23     cin >> n >> m >> k;
24     for(int i = 1; i <= m; i ++)
25     {
26         int x, y, z;
27         cin >> x >> y >> z;
28         edge[i].u = x;
29         edge[i].v = y;
30         edge[i].w = z;
31     }
32 
33     for(int i = 1; i <= n ; i ++)
34         p[i] = i;
35 
36     sort(edge + 1, edge + 1 + m, cmp);
37 
38     int h = 1;//记录到底几个节点
39     int js = 1; //计数已经加入几条边
40     while(js <= n - k) //k个树需要n-k条边
41     {
42         if(h > m)
43         {
44             cout << "No Answer" << endl;
45             return 0;
46         }
47         int x = edge[h].u, y = edge[h].v, w = edge[h].w;
48         int fx = getParent(x), fy = getParent(y);
49         if(fx != fy)
50         {
51             js ++;
52             p[fx] = fy;
53             ans += w;
54         }
55         h ++;
56     }
57 
58     if(js)  cout << ans;
59     return 0;
60 }