题解 | #还是畅通工程#

#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
const int MAX=100;

struct Edge{
    int from;
    int to;
    int length;
    bool operator<(const Edge& e)const{
        return length<e.length;
    }
};

Edge edge[MAX*MAX];
int father[MAX];
int height[MAX];

void Initialize(int n){
    for(int i=0;i<n;i++){
        father[i]= i;
        height[i]=0;
    }
    return;
}

int Find(int x){
    if(x!=father[x]){
        return Find(father[x]);
    }
    return father[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 edgeNumber){
    Initialize(n);
    sort(edge,edge+edgeNumber);
    int sum=0;
    for(int i=0;i<edgeNumber;i++){
        Edge current=edge[i];
        if(Find(current.from)!=Find(current.to)){
            Union(current.from,current.to);
            sum+=current.length;
        }
    }
    return sum;
}


int main(){
    int N;
    while(scanf("%d",&N)!=EOF){
        if(N==0){
            break;
        }
        int numD=N*(N-1)/2;
        int a,b,disAB;
        for(int i=0;i<numD;i++){
            scanf("%d %d %d",&edge[i].from,&edge[i].to,&edge[i].length);
        }
        int answer=Kruskal(N,numD);
        printf("%d\n",answer);
    }
    return 0;
}