C語言源碼： [cpp] #include<stdio.h> #include<stdlib.h> #include<math.h> #define maxsize 110 typedef struct edge { int a,b; double len; }edge; edge E[maxsize*(maxsize-1)/2]; int Tree[maxsize*(maxsize-1)/2]; int findroot(int x) { int temp; if(Tree[x]==-1) return x; else { temp=findroot(Tree[x]); Tree[x]=temp; return temp; } } int cmp(const void *a,const void *b) { struct edge *aa=(edge *)a; struct edge *bb=(edge *)b; return aa->len>bb->len?1:-1; } int main() { int n,i,j,top,roota,rootb; double point[maxsize][2],min; while(scanf("%d",&n)!=EOF) { for(i=0;i<n;i++) scanf("%lf %lf",&point[i][0],&point[i][1]); top=0; for(i=0;i<n-1;i++) { for(j=i+1;j<n;j++) { E[top].a=i; E[top].b=j; E[top].len=sqrt((point[i][0]-point[j][0])*(point[i][0]-point[j][0])+(point[i][1]-point[j][1])*(point[i][1]-point[j][1])); top++; } } qsort(E,top,sizeof(E[0]),cmp); for(i=0;i<top;i++) Tree[i]=-1; min=0; for(i=0;i<top;i++) { www.2cto.com roota=findroot(E[i].a); rootb=findroot(E[i].b); if(roota!=rootb) { Tree[rootb]=roota; min+=E[i].len; } } printf("%.2lf\n",min); } }
