HDU 1233 还是畅通工程
include<stdio.h>#include<algorithm>
using namespace std;
struct node{
int s,e;
int val;
}flag[5050];
int map[5050];
int n;
int cmp(node a,node b){
if(a.val<b.val)
return 1;
else return 0;
}
void init(){
for(int i=1;i<=n*(n-1)/2;i++)
map[i]=i;
}
int find(int x){
int r=x;
while(r!=map[r])
r=map[r];
int b=x;
int f;
while(b!=r){
f=map[b];
map[b]=r;
b=f;
}
return r;
}
int merge(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx!=fy){
map[fx]=fy;
return 1;
}
return 0;
}
int main(){
while(scanf("%d",&n)!=EOF){
if(n==0)break;
for(int i=0;i<n*(n-1)/2;i++){
scanf("%d%d%d",&flag[i].s,&flag[i].e,&flag[i].val);
}
sort(flag,flag+(n*(n-1)/2),cmp);
int sum=0,ans=0;
init();
for(int i=0;i<n*(n-1)/2;i++){
ans=merge(flag[i].s,flag[i].e);
if(ans)
sum+=flag[i].val;
}
printf("%d\n",sum);
}
return 0;
}
补充：软件开发 , C++ ,
