1 solutions
-
0
C++ :
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #include<algorithm> #include<iostream> using namespace std; int parent[105]; struct lu { int a,b; double length; }lu[10010]; struct point { double x,y; int num; }point[105]; int root(int p) { if(parent[p]==-1) return p; else return parent[p]=root(parent[p]); } void merge(int a,int b) { a=root(a); b=root(b); parent[a]=b; } int cmp(const void *a,const void *b) { struct lu *c,*d; c=(struct lu *)a; d=(struct lu *)b; if(c->length>d->length) return 1; if(c->length==d->length) return 0; if(c->length<d->length) return -1; } void ling() { int i,j,k; for(i=0;i<105;i++) parent[i]=-1; for(i=0;i<10010;i++) { lu[i].length=0.0; } } int main() { //freopen("B题测试数据.txt","r",stdin); //freopen("B题输出结果.txt","w",stdout); int i,j,k,l,m,n; double ans; while(scanf("%d",&n)!=EOF) { ling(); for(i=0;i<n;i++) { scanf("%lf%lf",&point[i].x,&point[i].y); } l=0; ans=0.0; for(i=0;i<n;i++) for(j=i+1;j<n;j++) { lu[l].a=i; lu[l].b=j; lu[l].length=sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y)); l++; } qsort(lu,l,sizeof(struct lu),cmp); for(i=0;i<n*n;i++) { if(root(lu[i].a)!=root(lu[i].b)) { merge(lu[i].a,lu[i].b); ans=ans+lu[i].length; } } printf("%.2lf\n",ans); } return 0; }
- 1
Information
- ID
- 17314
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- (None)
- Tags
- # Submissions
- 0
- Accepted
- 0
- Uploaded By