题解:
简单最小生成树
x,y都要double
我也不知道为什么
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=;
int n,m,f[N],xx,yy;
double x[N],y[N],a[N][N],dis[N],ans;
int main()
{
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)a[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
while (m--)
{
scanf("%d%d",&xx,&yy);
a[xx][yy]=a[yy][xx]=;
}
f[]=;
for (int i=;i<=n;i++)dis[i]=a[][i];
for (int i=;i<n;i++)
{
int l=-;
for (int j=;j<=n;j++)
if (!f[j]&&(l==-||dis[j]<dis[l]))l=j;
ans+=dis[l];
f[l]=;
for (int j=;j<=n;j++)
if (!f[j]&&dis[j]>a[l][j])dis[j]=a[l][j];
}
printf("%.2lf",ans);
}