请求加强数据
查看原帖
请求加强数据
470533
xjhawk楼主2024/10/19 12:31
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int t;
int k,n;
double a[N],b[N];
struct node{
	double x,y,d;
}e[N];
double ans;
int tot=0;
void _add(int x,int y)
{
	tot++;
	e[tot].x=x;
	e[tot].y=y;
	e[tot].d=1.0000*sqrt((a[x]-a[y])*(a[x]-a[y])+(b[x]-b[y])*(b[x]-b[y]));
	return ;
}
int fa[N];
int find(int x)
{
	if(fa[x]==x)
	{
		return x;
	}
	return fa[x]=find(fa[x]);
}
bool cmp(node p,node q)
{
	return p.d<q.d;
}
void ku()
{
	int tp=0;
	for(int i=1;i<=tot;i++)
	{
		int x=e[i].x,y=e[i].y;
		int tx=find(x),ty=find(y);
		if(tx!=ty)
		{
			fa[find(tx)]=find(ty);
			tp++;
			ans=max(ans,e[i].d);
			//cout<<ans<<endl;
			if(tp>=n-k)
			{
				return ;
			}
		}
	}
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    	cin>>k>>n;
    	tot=0;
    	if(n==k)
    	{
    	    cout<<"0.00";
    	    return 0;
    	}
    	memset(a,0,sizeof a);
    	memset(b,0,sizeof b);
    	for(int i=1;i<=n;i++)
    	{
    		cin>>a[i]>>b[i];
			for(int j=1;j<i;j++)
			{
				_add(i,j);
			} 
		}
		for(int i=1;i<=n;i++)
		{
			fa[i]=i;
		}
		sort(e+1,e+1+tot,cmp);
		ku();
		cout<<std::fixed<<setprecision(2)<<ans<<endl;
  	return 0;
}

后三个点全是特判,而前两个点在我

if(fa[x]==x)

打成了

if(fa[x]=x)

依然能过......

就觉得好好笑

2024/10/19 12:31
加载中...