九度教程第72题

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.zzzyk.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);  
    }  
}  
 

补充：软件开发 , C++ ,

上一个：九度教程第73题
下一个：九度教程第71题