#2#10 RE 求助大佬 or2
查看原帖
#2#10 RE 求助大佬 or2
1171003
zzz987楼主2024/1/23 20:56
#include<bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f
using namespace std;
const int N=1e3;
const int M=5e7+9;
int n,m;
struct strr{
	int xi,yi;
}point[N];
double f(strr i,strr j){
	return (i.xi-j.xi)*(i.xi-j.xi)+(i.yi-j.yi)*(i.yi-j.yi);
}
struct str{
	int x,y;
	int len;
}a[M];
int p[N];
bool cmp(str i,str j){
	return i.len<j.len;
}
int find(int x){
	if(p[x]!=x)	p[x]=find(p[x]);
	return p[x];
}
int k;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin >>n>>m;
	for(int i=1;i<=n;i++){
		p[i]=i;
		cin >>point[i].xi>>point[i].yi;
	}
	for(int i=1;i<=m;i++){
		int x,y;	cin >>x>>y;
		x=find(x),y=find(y);
		if(x!=y)	p[x]=y;
	}
	for(int i=1;i<n;i++){
		for(int j=i+1;j<=n;j++){
			int ti=find(i),tj=find(j);
			if(ti!=tj){
				k++;
				a[k].x=i,a[k].y=j;
				a[k].len=f(point[i],point[j]);
			}
		}
	}
//	for(int i=1;i<=k;i++){
//		cout <<a[i].x<<" "<<a[i].y<<" "<<a[i].len<<endl;
//	}
	sort(a+1,a+k+1,cmp);
	double ans=0;
	for(int i=1;i<=k;i++){
		int x=a[i].x,y=a[i].y;
		x=find(x),y=find(y);
		if(x!=y){
			p[x]=y;
			ans+=sqrt(a[i].len);
		}
	}
	printf("%.2lf",ans);
	return 0;
}
2024/1/23 20:56
加载中...