题解 | #Freckles#

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
/*重点是用getEnds判断是否形成回路，getEnds得到的结果是每条子树的最后一个节点*/
typedef struct Graph {
    int from;
    int to;
    double distance;
}Graph;
int cmp(const void*e1,const void*e2)
{
    if((*(Graph*) e1).distance>(*(Graph*)e2).distance)return 1;
    else if((*(Graph*)e1).distance<(*(Graph*)e2).distance)return -1;
    else return 0;
}
int getEnds(int ends[],int p)
{
    while(ends[p]!=0)p=ends[p];
    return p;
};
int main() {
    int n;
    scanf("%d",&n);
    double a[100][2];
    for(int i=0;i<n;i++)
    {
        scanf("%lf %lf",&a[i][0],&a[i][1]);
        //printf("%lf",a[i][1]);
    }
    double distance[100][100]={65535};
    for(int i=0;i<n;i++)
    {
        for(int j=i;j<n;j++)
        {
//            printf("%d %d %f %f %f %f\n",i,j,a[i][0],a[j][0],a[i][1],a[j][1]);
            distance[i][j]=sqrt(pow((a[i][0]-a[j][0]),2)+pow((a[i][1]-a[j][1]),2));
            //printf("%.2f\n",distance[i][j]);
            distance[j][i]=distance[i][j];
        }
    }
    Graph *g=(Graph*)malloc(sizeof(Graph)*n*n);
    int edge_num=0;
    for(int i=0;i<n;i++)
    {
        for (int j=i;j<n;j++) {
            g[edge_num].from=i;
            g[edge_num].to=j;
            g[edge_num].distance=distance[i][j];
            edge_num++;
        }
    }
    qsort(g,edge_num,sizeof(Graph),cmp);
    double sum=0;
    int ends[100]={0};

    //for(int i=0;i<n;i++)ends[i]=i;
    for(int i=0;i<edge_num;i++)
    {
        if(g[i].distance!=0)
        {
            //printf("%.2lf\n",g[i].distance);
            int p1 = getEnds(ends,g[i].from);
            int p2 = getEnds(ends,g[i].to);
            //printf("%d %d",p1,p2);
           if(p1!=p2)
            {
                //printf("aaa");
                sum+=g[i].distance;
                ends[p1]=p2;

            }
        }
    }
    //for(int i=0;i<edge_num;i++)printf("%.2lf\n",g[i].distance);
//    for(int i=0;i<n;i++)
//    {
//        if(choose[i]!=1)printf("%d:false\n",i);
//    }
    printf("%.2lf",sum);


    return 0;
}