RE四个点,求助
查看原帖
RE四个点,求助
406075
Qimu47楼主2022/8/22 21:06
#include <bits/stdc++.h>
#include <unordered_set>

#define x first
#define y second

using namespace std;

typedef long long ll;
const int N = 1e5 + 10;

struct E{
    int a,b;
    double w;
    bool operator<(const E &W)const{
        return w<W.w;
    }
}e[N];

int p[N];

int n,m;
int cnt;
double ans;
int x[N],y[N];

int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

double f(double a,double b,double c,double d)
{
    return (double)sqrt((double)(a-c)*(a-c)+(double)(b-d)*(b-d));
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            e[cnt++]={i,j,f(x[i],y[i],x[j],y[j])};
        }
    }
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        e[cnt++]={a,b,0};
    }
    sort(e,e+cnt);
    for(int i=0;i<cnt;i++)
    {
        int a=e[i].a,b=e[i].b;
        double w=e[i].w;
        if(find(a)!=find(b))
        {
            ans+=w;
            p[find(a)]=find(b);
        }
    }
    printf("%.2lf\n",ans);

    return 0;
}
2022/8/22 21:06
加载中...