题目
京海市城市规划部门计划修建一个大型地铁网络，将城市中的重要交通支点用地铁网络连接起来，以方便市民通行。 但是节点过多，预算不够，让京海市城市规划部门十分头疼，请你用计算机帮助他们进行设计这个网络，要求是在将重要交通支点连接起来的前提下，使修建地铁网络的费用最低。
Input
存在多组测试数据，每组数据包含所给定的地图要素信息：
每组数据的第一行包含两个整数：重要交通节点的数量 N 和可修建地铁路线的数量 M 。 重要交通节点的编号用 1 到 N 的整数代替。
之后的 M 行包含三个整数：前两个整数为地铁线路连接的两个节点的编号 a 和 b ，第三个整数为通过该线路连接这两个节点的花费 W 。
1≤N≤50
1≤M≤10^5
1≤W≤100
注意！！！若 N 为 0 ，则结束输入。
Output
对于每组测试数据，仅输出一行，包含一个整数：将所有关键节点连接起来的最低花费。 保证一定至少有一种方案，使得所有关键节点连通。
Sample
input:
1 0
2 3
1 2 37
2 1 17
1 2 68
3 7
1 2 19
2 3 11
3 1 7
1 3 5
2 3 89
3 1 91
1 2 32
5 7
1 2 5
2 3 7
2 4 8
4 5 11
3 5 10
1 5 6
4 2 12
0
output:
0
17
16
26
代码
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
int n, m; //n个点，m条边
int sum, ans, cnt; //sum记录连接的边数
int fa[MAXN];
struct node { //结构体
int x;//端点之一
int y;//端点之二
int w;//边权值
} a[MAXN];
int cmp(node x, node y) { //将数据按照从小到大的顺序排序
return x.w < y.w;
}
int find(int x) {
if (x == fa[x])
return x;
else {
fa[x] = find(fa[x]);
return fa[x];
}
}
void kruskal() {
for (int i = 1; i <= m; i++) {
cin >> a[i].x >> a[i].y >> a[i].w;
}
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
sort(a + 1, a + 1 + m, cmp);
for (int i = 1; i <= m; i++) { //加边
int x = find(a[i].x);
int y = find(a[i].y);
if (x != y) { //如果不在同一个集合
fa[y] = x; //合并
sum++;//边数加1
ans += a[i].w;
if (sum == n - 1) { //如果边数达到n-1，则寻找完毕
break;
}
}
}
}
int main() {
while (cin >> n) {
if (n == 0) break;
ans = 0;
sum = 0;
cin >> m;
kruskal();
cout << ans << endl;
}
return 0;
}