本文主要是介绍九度考研真题 浙大 2008-3浙大1028:继续畅通工程,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
//题目1028:继续畅通工程#include<iostream>
#include<algorithm>
using namespace std;
int Tree[1010];
int findRoot(int x){
if(Tree[x]==-1) return x;
else {
int tmp=findRoot(Tree[x]);
Tree[x]=tmp;
return tmp;
}
}
struct Edge{
int a,b;
int cost;
bool operator<(const Edge&A)const{
return cost<A.cost;
}
}edge[4000];
int main(){
int n;
while(cin>>n&&n!=0){
for(int i=0;i<n*(n-1)/2;i++){
cin>>edge[i].a>>edge[i].b>>edge[i].cost;
}
sort(edge,edge+n*(n-1)/2);
int ans=0;
for(int i=0;i<n*(n-1)/2;i++) Tree[i]=-1;
for(int i=0;i<n*(n-1)/2;i++){
int a=findRoot(edge[i].a);
int b=findRoot(edge[i].b);
if(a!=b){
Tree[a]=b;
ans+=edge[i].cost;
}
} cout<<ans<<endl;
}
}
这篇关于九度考研真题 浙大 2008-3浙大1028:继续畅通工程的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!