题解 | #还是畅通工程#

#include <iostream>
#include <queue>
using namespace std;
const int maxn=100;
int father[maxn];
int height[maxn];
int findfather(int x){
    if(father[x]!=x) father[x]=findfather(father[x]);
    return father[x];
}
void Union(int x,int y){
    x=findfather(x);
    y=findfather(y);
    if(height[x]>height[y]) father[y]=x;
    else if(height[x]<height[y]) father[x]=y;
    else{
        father[y]=x;
        height[x]++;
    }
}
struct edge{
    int begin;
    int end;
    int length;
    edge(int a,int b,int c):begin(a),end(b),length(c){}
    bool operator< (edge b) const{
        return length>b.length;
    }
};
priority_queue<edge> q;
void init(){
    while (!q.empty()) {
    q.pop();
    }
    for(int i=0;i<maxn;i++){
        height[i]=0;
        father[i]=i;
    }
}
int main() {
    int n;
    while(cin>>n && n!=0){
    init();
    int t=n*(n-1)/2;
    for(int i=0;i<t;i++){
        int a,b,c;
        cin>>a>>b>>c;
        q.push(edge(a,b,c));
    }
    int r=0;
    while(!q.empty()){
        edge e=q.top();
        if(findfather(e.begin)!=findfather(e.end)){
            Union(e.begin,e.end);
            r+=e.length;
        }
        q.pop();
    }
    cout<<r<<endl;

    }


}