40分求助!!!
查看原帖
40分求助!!!
475143
gaojian2007楼主2021/10/3 11:43
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int s,n,m,x[10100],y[10100],fa[10100],k;
double ans;
struct sb
{
	int l;
	int r;
	double q;
}a[1000005];
double jl(int x2,int y2,int x1,int y1)
{
	return (double)sqrt((double)pow(x1-x2,2)+(double)pow(y1-y2,2));
}
bool cmp(sb q, sb w)
{
	return q.q<w.q;
}
int find(int xx)
{
	if(fa[xx]==xx)return xx;
	return fa[xx]=find(fa[xx]);
}
int main()
{
	cin>>s>>n;
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
		cin>>x[i]>>y[i];
		for(int j=1;j<i;j++)
		{
			a[++m].l=i;
			a[m].r=j;
			a[m].q=jl(x[i],y[i],x[j],y[j]);
		}
	}
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		int xx=find(a[i].l),yy=find(a[i].r);
		if(x!=y)
		{
			fa[xx]=yy;
			ans=a[i].q;
			k++;
			if(k>=n-s)break;
		}
	}
	printf("%0.2lf",ans);
	return 0;
} 
2021/10/3 11:43
加载中...