10pts求调,马蜂还算良好
查看原帖
10pts求调,马蜂还算良好
789404
Prosecutor_Godot_楼主2023/10/26 15:47
#include<bits/stdc++.h>
using namespace std;

struct edge{long long x,y,w;}e[500000];
bool cmp(edge &e1,edge &e2){return e1.w<e2.w;}
struct point{long long x,y;}p[1001];
istream &operator>>(istream &in,point &p1){
    in >> p1.x >> p1.y;return in;}
long long m,n;
long long f[1001];
long long edge_cnt=0;
double edge_num=0;
long long cnt=0;

long long ask(long long x){return x==f[x] ? x:f[x]=ask(f[x]);}
double dis(long long i,long long j){
    long long x1=p[i].x,x2=p[j].x;
    long long y1=p[i].y,y2=p[j].y;
    double x3=double(x1-x2);x3*=x3;
    double y3=double(y1-y2);y3*=y3;
    return sqrt(x3+y3);
}
int main(){

    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin >> n >> m;
    for(long long i=1;i<=n;i++) f[i]=i;

    for(long long i=1;i<=n;i++) cin >> p[i];
    //unknown edges adding
    for(long long i=1;i<=n-1;i++){
        for(long long j=i+1;j<=n;j++){
            e[++edge_cnt].x=i;e[edge_cnt].y=j;
            e[edge_cnt].w=dis(i,j);
        }
    }
    //known edges adding
    for(long long i=1;i<=m;i++){
        long long x,y;cin >> x >> y;
        e[++edge_cnt].x=x;e[edge_cnt].y=y;
        e[edge_cnt].w=0;
    }
    sort(e+1,e+edge_cnt+1,cmp);

    //krus
    for(long long i=1;i<=edge_cnt;i++){
        long long x=e[i].x,y=e[i].y;
        if(ask(x)!=ask(y)){
            edge_num+=e[i].w;
            f[ask(x)]=ask(f[y]);
            cnt++;
            if(cnt==n-1) break;
        }
    }

    //output
    cout << fixed << setprecision(2) << edge_num;

    return 0;
}

2023/10/26 15:47
加载中...