60分,回复必关。
查看原帖
60分,回复必关。
755531
zz2013楼主2023/1/7 19:21
#include<bits/stdc++.h>
using namespace std;
int fa[500010];
struct node{
	int x,y;
}a[500010];
struct node2{
	int ii,jj;
	double w;
}b[500010];
double dis(int xx,int xy,int yx,int yy){
	return sqrt((yx-xx)*(yx-xx)+(yy-xy)*(yy-xy));
}
int find(int x){
	if(fa[x]==x){
		return x;
	}
	return fa[x]=find(fa[x]);
}
void build(int x,int y){
	int fx=find(x),fy=find(y);
	if(fx==fy){
		return;
	}
	fa[fx]=fy;
}
bool same_set(int x,int y){
	int fx=find(x),fy=find(y);
	if(fx==fy){
		return 1;
	}
	return 0;
}
bool cmp(node2 i,node2 j){
	return i.w<j.w;
}
int main(){
	int n,m,cnt=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y;
	}
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		build(x,y);
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			cnt++;
			b[cnt].ii=i;
			b[cnt].jj=j;
			b[cnt].w=dis(a[i].x,a[i].y,a[j].x,a[j].y);
		}
	}
	sort(b+1,b+cnt+1,cmp);
	double sum=0;
	for(int i=1;i<=cnt;i++){
		if(same_set(b[i].ii,b[i].jj)==0){
			sum+=b[i].w;
		}
		build(b[i].ii,b[i].jj);
	}
	printf("%.2lf",sum);
	return 0;
}
2023/1/7 19:21
加载中...