无助40分
查看原帖
无助40分
507170
zhn2016楼主2022/10/16 20:26
#include<bits/stdc++.h>
using namespace std;
int p[100111];
int find(int x){
    return p[x]==x?x:p[x]=find(p[x]);
}
struct N{
    int a,b;
    double w;
}e[10010101];
bool cmp(N a,N b){
    return a.w<b.w;
}
int main(){
    int n,m;
    cin>>n>>m;
    int x[1011]={},y[1010]={};
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
        p[i]=i;
    }
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        p[a]=b;
    }
    int s=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i<=j)continue;
            double t=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
            e[++s]={i,j,t};
        }
    }
    double u=0;
    sort(e+1,e+s+1,cmp);
    for(int i=1;i<=s;i++){
        int a=find(e[i].a),b=find(e[i].b);
        double w=e[i].w;
        if(a!=b){
            p[a]=b;
            u+=w;
        }
    }
    printf("%.2lf",u);
    
}
2022/10/16 20:26
加载中...