50分求助
查看原帖
50分求助
1331245
king___y楼主2024/12/16 19:15
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,l,r,c,fa[2000001],cnt,nn;
double ans;
struct ac{
	ll x,y;
	ll z;
}a[2000005];
ac bb[2000001];
ll zhao(ll x){
	if(fa[x]!=x) fa[x]=zhao(fa[x]);
	return fa[x];
}
bool cmp(ac a,ac b){
	return a.z<b.z;
}
int main(){
	cin>>m>>c;
	for(ll i=1;i<=m;i++){
		fa[i]=i;
	}
	for(ll i=1;i<=m;i++){
		cin>>bb[i].x>>bb[i].y;
		for(ll j=1;j<i;j++){
			if((long long)(bb[i].x-bb[j].x)*(bb[i].x-bb[j].x)+(bb[j].y-bb[i].y)*(bb[j].y-bb[i].y)>=c){
				a[++nn].x=i;
				a[nn].y=j;
				a[nn].z=(long long)(bb[i].x-bb[j].x)*(bb[i].x-bb[j].x)+(bb[j].y-bb[i].y)*(bb[j].y-bb[i].y);
			}
			
		}
	}
	sort(a+1,a+1+nn,cmp);
	for(ll i=1;i<=nn;i++){
		ll xx=zhao(a[i].x),yy=zhao(a[i].y);
		if(xx==yy){	
			continue;
		}
		fa[yy]=xx;
		cnt++;
		ans+=a[i].z;
		if(cnt==m-1){
			cout<<ans;
			return 0;
		}
	}
	cout<<-1;
	return 0;
}
2024/12/16 19:15
加载中...