洛谷 P2872 道路建设

https://www.luogu.org/problemnew/show/P2872

算是比较裸的并查集了，已经有路的两个点之间建一条代价为0的边，路径长度计算两点之间的距离，做并查集就好咯。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define Ldouble long double
#define LL long long
int n,m,tot;
struct ahah{
    int x,y;
    Ldouble dis;
}a[2000006];
LL fa[1006],_,__,cnt;

Ldouble calc(Ldouble x1,Ldouble y1,Ldouble x2,Ldouble y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int find(int x)
{
    return fa[x]==x?x:find(fa[x]);
}
bool cmp(ahah a,ahah b)
{
    return a.dis<b.dis;
}
Ldouble x[1006],y[1006],___;
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=n;i++)scanf("%Lf%Lf",&x[i],&y[i]);
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            a[++tot].x=i;
            a[tot].y=j;
            a[tot].dis=calc(x[i],y[i],x[j],y[j]);
        }
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld",&_,&__);
        a[++tot].x=_;
        a[tot].y=__;
        a[tot].dis=0;
    }
    sort(a+1,a+1+tot,cmp);
    for(int i=1;i<=tot;i++)
    {
        int g=find(a[i].x),h=find(a[i].y);
        if(g!=h)
        {
            fa[g]=h;
            ___+=a[i].dis;
            cnt++;
            if(cnt==n-1)break;
        }
    }
    printf("%.2Lf",___);
}