ACM | 还是畅通工程

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

输入格式:

测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。 当N为0时，输入结束，该用例不被处理。

输出格式:

对每个测试用例，在1行里输出最小的公路总长度。

输入样例:

3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0

输出样例:

3
5

代码样例：

#include<stdio.h>
#include<string.h>
int satellite_city[100+1];
// void swap(int *a,int *b){
//     int t=*a;
//     *a=*b;
//     *b=t;
// }
int compare(const void *a, const void *b) {
    return ((int*)a)[2] - ((int*)b)[2];
}
void merge(int a,int b,int n){
    if(a>b){
        int t=a;
        a=b;
        b=t;
    }
    for(int i=1;i<=n;i++){
        if(satellite_city[i]==b){
            satellite_city[i]=a;
        }
    }
}
int check(int n){
    for(int i=1;i<=n-1;i++){
        if(satellite_city[i]!=satellite_city[i+1]){
            return 1;  //1表示还有未连接的城市
        }
    }
    return 0;
}
int main(){
    int N,M;
    scanf("%d",&N);
    int roads[5050+1][3];
    while(N!=0){
        M=N*(N-1)/2;
        for(int i=1;i<=N;i++){  //初始化每个城镇都是独立城市
            satellite_city[i]=i;
        }
        for(int i=0;i<M;i++){  //读取路
            scanf("%d%d%d",roads[i],roads[i]+1,roads[i]+2);
        }
        // for(int i=0;i<M;i++){  //根据路的距离从小到大排序
        //     for(int j=0;j<M-i-1;j++){
        //         if(roads[j][2]>roads[j+1][2]){
        //             for(int o=0;o<3;o++){
        //                 swap(&roads[j][o],&roads[j+1][o]);
        //             }
        //         }
        //     }
        // }

        // 使用qsort进行排序
        qsort(roads, M, sizeof(roads[0]), compare);
        
        int ans=0;
        int cur=0; //标记当前的路
        while(check(N)){
            if(satellite_city[roads[cur][0]]!=satellite_city[roads[cur][1]]){
                merge(satellite_city[roads[cur][0]],satellite_city[roads[cur][1]],N);
                ans+=roads[cur][2];
            }
            cur++;
        }
        printf("%d\n",ans);
        scanf("%d",&N);
    }
    return 0;
}