题解 | #还是畅通工程#

#include <iostream>
//#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;

const int MAXN=100;
struct Edge
{
    int point1,point2,weight;
    Edge(int p1,int p2,int w):point1(p1),point2(p2),weight(w){};
    Edge(){};
    
};
bool cmp(const Edge & e1,const Edge & e2) 
{
    return e1.weight<e2.weight;
}
int _rank[MAXN];
int father[MAXN];
void intialize(int n)
{
    for(int i=0;i<n;++i)
    {
        father[i]=i;
        _rank[i]=1;
    }
}

int find(int x)
{
    if(x==father[x])
        return x;
    return father[x]=find(father[x]);
}
void _union(int x,int y)
{
    x=find(x);
    y=find(y);
    if(_rank[x]<_rank[y])
        father[x]=y;
    else if(_rank[y]<_rank[x])
        father[y]=x;
    else
    {
        father[x]=y;
        ++_rank[y];
    }
}

int main() 
{
    int n,numE,ans;
    while(cin>>n)
    {
        if(n==0) break;
        ans=0;
        numE=n*(n-1)/2;
        Edge edge[numE];
        intialize(n);
        for(int i=0;i<numE;++i)
        {
            int tp1,tp2,tw;
            cin>>tp1>>tp2>>tw;
            edge[i]=Edge(tp1-1,tp2-1,tw);
        }
        sort(edge,edge+numE,cmp);
        for(int i=0;i<numE;++i)
        {
            Edge tedge=edge[i];
            if(find(tedge.point1)!=find(tedge.point2))
            {
                ans+=tedge.weight;
                _union(tedge.point1,tedge.point2);
            }
        }
        cout<<ans<<endl;

    }


}
// 64 位输出请用 printf("%lld")