题解 | #还是畅通工程#

#include <iostream>
#include <algorithm>
using namespace std;
const int N=102;
//边结点
struct Edge{
    int from;
    int to;
    int length;
    bool operator<(const Edge& e)const{
        return length<e.length;
    }
};
Edge edge[N*N]; //存储图的所有边结点
int father[N];
int height[N];
void Initial(int n){
    for(int i=0;i<n;i++){
        father[i]=i;
        height[i]=0;
    } 
}
int Find(int x){
    while(father[x]!=x) x=father[x];
    return x;
}
void Union(int x,int y){
    x=Find(x);
    y=Find(y);
    if(x!=y){
        if(height[x]<height[y]) father[x]=y;
        else if(height[y]<height[x]) father[y]=x;
        else {
            father[y]=x;
            height[x]++;
        } 
    }
    return;
}
int Kruskal(int n,int edgeNum){  //总共结点数，总共边数
    int sum=0;
    Initial(n);
    sort(edge,edge+edgeNum);
    for(int i=0;i<edgeNum;i++){
        if(Find(edge[i].from)!=Find(edge[i].to)){
            Union(edge[i].from,edge[i].to);
            sum+=edge[i].length;
        }
    }
    return sum;
}
int main(){
    int n;
    while(cin>>n){
        if(n==0) break;
        int m=n*(n-1)/2;
        for(int i=0;i<m;i++) cin>>edge[i].from>>edge[i].to>>edge[i].length;
        int ans=Kruskal(n,m);
        cout<<ans<<endl;
    }
    return 0;
}