70268 - CSP-J第一轮同测模拟卷1-完善程序2
统计题目(材料题)
（最小生成树）给定一个 n 个顶点m 条边的无向连通图，每条边有边权，求最小生成树的总权值。使用 Kruskal 算法，需要实现并查集的查找和合并操作。
01 #include <iostream>
02 #include <algorithm>
03 using namespace std;
04
05 struct Edge {
06 int u, v, w;
07 };
08
09 int n, m;
10 Edge edges[10000];
11 int parent[105], rank[105];
12
13 bool cmp(Edge a, Edge b) {
14 return a.w < b.w;
15 }
16
17 int find(int x) {
18 if (parent[x] == x) return x;
19 return ①;
20 }
21
22 void unite(int x, int y) {
23 int rx = find(x), ry = find(y);
24 if (rx == ry) return;
25 if (rank[rx] < rank[ry]) {
26 parent[rx] = ry;
27 } else if (rank[rx] > rank[ry]) {
28 parent[ry] = rx;
29 } else {
30 parent[ry] = rx;
31 ②;
32 }
33 }
34
35 int main() {
36 cin >> n >> m;
37 for (int i = 0; i < m; i++) {
38 cin >> edges[i].u >> edges[i].v >> edges[i].w;
39 }
40 ③;
41 for (int i = 1; i <= n; i++) {
42 parent[i] = i;
43 rank[i] = 0;
44 }
45 int cnt = 0, ans = 0;
46 for (int i = 0; i < m; i++) {
47 if (④) {
48 unite(edges[i].u, edges[i].v);
49 ⑤ ;
50 cnt++;
51 if (cnt == n - 1) break;
52 }
53 }
54 cout << ans << endl;
55 return 0;
56 }
关注我们
