记录编号	581243	评测结果	AAAAAAAAAA
题目名称	[USACO Dec07] 建造路径	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.201 s
提交时间	2023-07-31 17:48:54	内存使用	14.58 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N = 10010,M = 2000010;
int n,m;
struct node{
    double x,y;
}a[N];
struct made{
    int x,y;
    double z;
}d[M];
int fa[N],tot;
double ans;
double dis(node x,node y){
    return sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y));
}//距离 
int find(int x){
    if(x == fa[x])return x;
    return fa[x] = find(fa[x]);
}
bool cmp(made x,made y){
    return x.z < y.z;
}
int main(){
    freopen("roads.in","r",stdin);
    freopen("roads.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++){
        scanf("%lf%lf",&a[i].x,&a[i].y);
        fa[i] = i;//顺便初始化 
    }
    for(int i = 1;i <= n;i++){
        for(int j = i+1;j <= n;j++){
            d[++tot] = {i,j,dis(a[i],a[j])};
        }//边 
    }
    for(int i = 1;i <= m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        if(find(x) == find(y))continue;
        fa[find(x)] = find(y);//!!!必须将祖先连一起！！！(并查集错误) 
    }
    sort(d+1,d+1+tot,cmp);
    for(int i = 1;i <= tot;i++){
        int x = find(d[i].x),y = find(d[i].y);
        if(x == y)continue;
        fa[x] = y;
        ans += d[i].z;
    }//kruskal 
    printf("%.2lf\n",ans);
    
    return 0;
    
}