还是畅通工程

还是畅通工程

Time Limit: 4000/2000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 20531????Accepted Submission(s): 9117

#include<cstdio>#include<algorithm>using namespace std;typedef struct{int from;int to;int len;}road;int cmp(road a,road b){return a.len<b.len;}road num[5000];int root[105];int find(int a){int x=a,temp;//找根节点while(root[x]!=x) x=root[x];//压缩路径while(x!=a) { temp=root[a]; root[a]=x; a=temp; }return x;}int main(){int n;while(scanf("%d",&n)!=EOF){ int sum=0; if(n==0) break;//初始化根节点 for(int i=1;i<=105;i++) root[i]=i;//输入边 for(int i=1;i<=(n*(n-1))/2;i++) scanf("%d%d%d",&num[i].from,&num[i].to,&num[i].len);//对边排序 sort(num+1,num+(n*(n-1))/2+1,cmp);//排序后扫描边 for(int i=1;i<=(n*(n-1))/2;i++) { int fa,fb; fa=find(num[i].from); fb=find(num[i].to);//如果已经在一个连通图上，则放弃这条边 if(fa==fb) continue;//不在则合并顶点，总长加上这条边的权 else { root[fa]=fb; sum+=num[i].len; } }//输出该边 printf("%d\n",sum);}return 0;}