10pts求助
查看原帖
10pts求助
668379
Poole_tea楼主2023/1/16 20:28
#include<bits/stdc++.h>
using namespace std;
struct farm{
	int u,v,w;
}a[20081128];
int tot,fa[20081128];
bool cmp(farm a,farm b)
{
	return a.w<b.w;
}
int find(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
} 
void add(int x,int y,int z)
{
	a[++tot].u=x;
	a[tot].v=y;
	a[tot].w=z;
}
int x[20081128],y[20081128];
int main()
{
	int n,m,z,ans=0,t=0;
	cin>>n>>m;
	for(int i=0;i<=n;i++)
	{
		fa[i]=i;
	} 
	for(int i=1;i<=n;i++)
	{
		cin>>x[i]>>y[i];
		for(int j=1;j<i;j++)
		{
			z=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
			if(z>=m)
			{
				add(i,j,z);
			}
		}
	}
	sort(a+1,a+tot+1,cmp);
	for(int i=1;i<=tot;i++)
	{
		int x1,x2;
		x1=find(a[i].u);
		x2=find(a[i].v);
		if(x1!=x2)
		{
			fa[x1]=x2;
			ans+=a[i].w;
			t++;
		}
		if(t==n-1)
		{
			cout<<ans;
			return 0;
		}
	}
	cout<<-1;
	return 0;
}
2023/1/16 20:28
加载中...