题解 | #还是畅通工程#

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

struct Road {
    int a,b,cost;
};
bool isShort(Road a,Road b){
    return a.cost<b.cost;
}
int getRoot(map<int,int> &m,int i){
    if(m.find(i)==m.end()) m[i] = i;
    while(m[i]!=i){
        i = m[i];
    }
    return i;
}
int main(){
    int N;
    int a,b,cost;
        
    while(cin>>N){
        if(N==0) break;
        
        vector<Road> roads;
        map<int,int> nodes;
        int len = N*(N-1)/2;
        for(int i=0;i<len;i++){
            Road r;
            cin>>r.a>>r.b>>r.cost;
            roads.push_back(r);
        }
        sort(roads.begin(),roads.begin()+roads.size(),isShort);
        
        int total = 0;
        for(int i=0;i<roads.size();i++){
            int root_a = getRoot(nodes,roads[i].a);
            int root_b = getRoot(nodes,roads[i].b);
            if(root_a!=root_b){
                nodes[root_a] = root_b;
                total += roads[i].cost;
            }
        }
        cout<<total<<endl;
    }
    
    
    return 0;
}