题解 | Freckles

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
using namespace std;

int fa[1010];
int find(int x)
{
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}

typedef struct node{//点
    float x;
    float y;
    // float len;
}N;

typedef struct edge{//边
    int a,b;
    float len=0;
}E;

N no[110];

bool cmp(E e1,E e2)
{
    return e1.len<e2.len;
}

int main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>no[i].x>>no[i].y;
    }
    for(int i=1;i<=n;i++)fa[i]=i;
    int len=0;
    int s =n*(n+1)/2+1;
    E e[s];
    for(int i=1;i<n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            e[len].a = i;
            e[len].b = j;
            float lenth = (no[i].x-no[j].x)*(no[i].x-no[j].x)+(no[i].y-no[j].y)*(no[i].y-no[j].y);
            e[len].len = sqrt(lenth);//求边的长度
            len++;
        }
    }
    sort(e,e+len,cmp);
    int cnt=0;
    float ans=0;
    for(int i=0;i<len;i++)
    {
        int f1 = find(e[i].a);
        int f2 = find(e[i].b);
        if(f1!=f2)
        {
            fa[f1] = f2;
   //         cout<<e[i].len<<endl;
            ans +=e[i].len;
        }
        if(cnt==n-1)break;
    }
    printf("%.2lf",ans);

    

}