代码:
#include<bits/stdc++.h>
#define double long double
using namespace std;
struct node{
double x,y;
inline void read()
{
cin>>x>>y;
}
}a[20009];
int f[20009],p[2009][2009];
struct E{
int u,v;
double w;
}e[20009];
int et;
inline double dis(int X,int Y)
{
return (double)(sqrt((a[X].x-a[Y].x)*(a[X].x-a[Y].x)+(a[X].y-a[Y].y)*(a[X].y-a[Y].y)));
}
inline bool cmp(E x,E y)
{
return x.w<y.w;
}
inline int find(int x)
{
if(f[x]!=x) f[x]=find(f[x]);
return f[x];
}
signed main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
a[i].read();
f[i]=i;
}
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
p[u][v]=p[v][u]=1;
e[++et].u=u;
e[et].v=v;
e[et].w=0;
}
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
if(!p[i][j]) e[++et].u=i,e[et].v=j,e[et].w=dis(i,j);
}
int tops=0;
double ans=0;
sort(e+1,e+et+1,cmp);
for(int i=1;i<=et;i++)
{
int tx=find(e[i].u),ty=find(e[i].v);
if(tx!=ty)
{
f[tx]=ty;
ans+=e[i].w;
if(++tops>=n-1) break;
}
}
cout<<fixed<<setprecision(2)<<ans;
return 0;
}
谁能帮帮忙