玄关,#10MLE
查看原帖
玄关,#10MLE
1035256
white_ice楼主2024/7/5 09:07
//2024.7.5
//by white_ice
//[USACO07DEC] Building Roads S | P2872
#include<bits/stdc++.h>
//#include"need.cpp"
using namespace std;
#define itn int
constexpr int oo = 1003;

int n,m;

pair<int,int> sp[oo];

struct ed{int x,y;double w;}edge[oo*oo];
int cnt;
bool cmp(ed a,ed b){return a.w<b.w;}

int fa[oo];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

// struct nod{int v,nxt;}st[oo];
// int head[oo],top;
// void add(itn a,itn b){
//     st[++top].v = b;
//     st[top].nxt = head[a];
//     head[a] = top;
// }

int main(){
    //fre();

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

    cin >> n >> m;
    for (itn x,y,i=1;i<=n;i++){
        cin >> x >> y;
        sp[i].first = x;
        sp[i].second = y;
    }

    for (itn i=1;i<=n;i++)
        fa[i] = i;

    for (itn x,y,i=1;i<=m;i++){
        cin >> x >> y;
        //add(x,y); add(y,x);
        int u = find(x);
        int v = find(y);
        fa[u] = y;
    }
    
    for (int i=1;i<=n;i++){
        for (int j=i;j<=n;j++){
            // if (find(i)==find(j))
            //     continue;
            double w = ((double)(sp[i].first-sp[j].first)*(sp[i].first-sp[j].first)+(double)(sp[i].second-sp[j].second)*(sp[i].second-sp[j].second));
            edge[++cnt].x = i;
            edge[cnt].y = j;
            edge[cnt].w = w;
        }
    }

    sort(edge+1,edge+cnt+1,cmp);

    int sum = 0;
    double sumf = 0;
    for (itn i=1;i<=cnt;i++){
        int x = find(edge[i].x);
        int y = find(edge[i].y);
        if (x==y)       
            continue;
        fa[x] = y;
        sum ++;
        sumf += sqrt(edge[i].w);
        if (sum == n-1-m)
            break;
    }
    printf("%.2lf",sumf);

    return 0;
}

2024/7/5 09:07
加载中...