题解 | #还是畅通工程#

//最小生成树：边权和最小的一棵树
#include <iostream>
#include<algorithm>
using namespace std;

struct Edge{
    int from;
    int to;
    int length;

    bool operator<(const Edge& e)const{
        return length<e.length;
    }

};

Edge edge[5000];
int father[100];
int height[100];

void Initial()
{
    for(int i=0;i<100;i++)
    {
        father[i]=i;
        height[i]=0;
    }
}

int Find(int x)
{
    if(x==father[x])return x;
    else{
        return Find(father[x]);
    }
}

void Union(int a,int b)
{
    a=Find(a);
    b=Find(b);
    if(a!=b)
    {
        if(height[a]>height[b])father[b]=a;
        else if(height[a]<height[b])father[a]=b;
        else
         {
            father[b]=a;
            height[a]++;
         }
    }
}

int Kruskal(int n,int edgenumber)
{
    int answer=0;
    for(int i=0;i<edgenumber;i++)
    {
        if(Find(edge[i].from)!=Find(edge[i].to))
        {
            Union(edge[i].from,edge[i].to);
            answer+=edge[i].length;
        }
    }
    return answer;
}

int main() {
    int n;
    while (cin >> n) { 
        if(n==0)break;
        int edgenumber=n*(n-1)/2;
       
        for(int i=0;i<edgenumber;i++)
        {
            cin>>edge[i].from>>edge[i].to>>edge[i].length;
        }
        sort(edge,edge+edgenumber);
        Initial();
        cout<<Kruskal(n,edgenumber)<<endl;
    }
}