想用Kruskal
但是不知道错在哪里
#include <bits/stdc++.h>
using namespace std;
const int EDG=1000010;
int parent[EDG];
void init();
int find(int x);
int union_(int x,int y);
int search_(int x,int y);
int n,m;
struct edg
{
int st,ed;
double we;
} arc[EDG];
int tot=0;
void add(int x,int y,double z)
{
arc[++tot].we=z;
arc[tot].st=x;
arc[tot].ed=y;
}
struct node
{
double x,y;
} ver[EDG];
bool cmp(edg a,edg b)
{
return a.we<b.we;
}
double distance(int x1,int x2,int y1,int y2)
{
double tmp=(double)sqrt((double)(x2-x1)*(double)(x2-x1)+(double)(y2-y2)*(double)(y2-y1));
return tmp;
}
int main()
{
init();
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>ver[i].x>>ver[i].y;
}
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
add(i,j,distance(ver[i].x,ver[j].x,ver[i].y,ver[j].y));
}
}
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
add(x,y,0.0);
}
sort(arc+1,arc+1+tot,cmp);
int num=0;
double ans=0;
for(int i=1;i<=tot;i++)
{
if(!search_(arc[i].st,arc[i].ed))
{
ans+=arc[i].we;
num++;
union_(arc[i].st,arc[i].ed);
}
}
cout<<fixed<<setprecision(2)<<ans;
return 0;
}
void init()
{
for(int i=0;i<EDG;i++)
{
parent[i]=i;
arc[i].we=0x3f3f3f3f;
}
}
int find(int x)
{
int x_root=x;
while(x_root!=parent[x_root])
{
x_root=parent[x_root];
}
while(x_root!=x)
{
int tmp=parent[x];
parent[x]=x_root;
x=tmp;
}
return x_root;
}
int union_(int x,int y)
{
int x_root=find(x);
int y_root=find(y);
if(x_root==y_root) return 0;
parent[x_root]=y_root;
return 1;
}
int search_(int x,int y)
{
return find(x)==find(y);
}