最小生成树 Kruskal

java c++

Description
为完成国家规定的“村村通”项目基本要求，某省加快了农村基层道路建设的脚步，该项目要求对于各个村庄都可以实现公路交通到达任意的另一个村庄（但不一定有直接的公路相连，只要能间接通过公路可达即可），为了节省经费，省内要求铺设方案使得公路总长度为最小。请你计算该最小的公路总长度。

Input
测试输入包含多组样例。每组的第1行给出村庄数目n(n<100),随后的n(n-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到n编号。

当n为0时，输入结束，该样例不被处理。

Output
每组数据输出一行，为最小的公路总长度。

Sample Input
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
Sample Output
3
5

C++ 实现

#include<iostream>
#include<math.h>
#include<vector>
#include<memory.h>
#include<algorithm>
using namespace std;
int par[100];
bool vis[100];
struct edge{
    int s;
    int t;
    int w;
};
bool compare(edge a, edge b){
    return a.w < b.w;
}
int findpar(int i){
    return par[i]==i?i:findpar(par[i]);
}
int main(){
    int n;
    while(cin >> n){
        if(n==0) break;
        int sum = (n*(n-1))/2;
        edge es[sum];
        memset(par,0,sizeof(par));
        memset(vis,0,sizeof(vis));
        for(int i=0; i<sum; i++){
            cin >> es[i].s >> es[i].t >> es[i].w;
        }
        for(int i=0;i<n;i++){
            par[i] = i;
        }
        sort(es,es+sum,compare);
        int count = 0;
        for(edge &e : es){
           if(findpar(e.s) != findpar(e.t)){
                par[findpar(e.t)] = e.s;
                count += e.w;
           }
        }
        cout << count << endl;
    }
}