学步园

题目链接：点击打开链接

还是很基础的最小生成树

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=105;
const int Max=5005;
int n,top,father[N];
struct Point
{
    double x,y;
}point[N];
struct Line
{
    double a,b;
    double lenth;
}line[Max];
bool cmp(Line A,Line B)
{
    if(A.lenth<B.lenth) return true;
    return false;
}
void Init()
{
    for(int i=0;i<=n;i++)
    father[i]=i;
    top=0;
}
void input()
{
    for(int i=1;i<=n;i++)
    scanf("%lf%lf",&point[i].x,&point[i].y);
    for(int i=1;i<=n;i++)//直接枚举所有的连线进行排序.
    {
        for(int j=i+1;j<=n;j++)
        {
            line[top].a=i;
            line[top].b=j;
            line[top].lenth=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));
            top++;
        }
    }
}
int find(int x)
{
    if(x!=father[x])
    father[x]=find(father[x]);
    return father[x];
}
void kruscal()
{
    double min=0;
    sort(line,line+top,cmp);
    for(int  i=0;i<top;i++)
    {
        int x=find(line[i].a);
        int y=find(line[i].b);
        if(x!=y)
        {
            father[x]=y;
            min+=line[i].lenth;
        }
    }
    printf("%.2lf\n",min);
}
int main()
{
    while(~scanf("%d",&n))
    {
        Init();
        input();
        kruscal();
    }
}

1A