题解 | #还是畅通工程#
还是畅通工程
http://www.nowcoder.com/practice/d6bd75dbb36e410995f8673a6a2e2229
基于并查集实现克鲁斯卡尔算法
两个端点不再同一集合中则union
#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;
}
