【BZOJ1821】[JSOI2010]部落划分（二分，并查集）

题面

题解

二分答案，把距离小于二分值的点全部并起来，\(\mbox{check}\)一下是否有超过\(K\)个集合就好了。

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

#define MAX 1010

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int f[MAX],x[MAX],y[MAX],n,K;

double Sqr(double x){return x*x;}

double Dis(int i,int j){return sqrt(Sqr(x[i]-x[j])+Sqr(y[i]-y[j]));}

int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}

bool check(double mid)

{

	for(int i=1;i<=n;++i)f[i]=i;

	for(int i=1;i<=n;++i)

		for(int j=i+1;j<=n;++j)

			if(Dis(i,j)<=mid)f[getf(j)]=getf(i);

	int tot=0;

	for(int i=1;i<=n;++i)if(i==getf(i))++tot;

	return tot>=K;

}

int main()

{

	n=read();K=read();

	for(int i=1;i<=n;++i)x[i]=read(),y[i]=read();

	double l=0,r=2e4;

	while(r-l>1e-4)

	{

		double mid=(l+r)/2;

		if(check(mid))l=mid;

		else r=mid;

	}

	printf("%.2lf\n",l);

	return 0;

}

巴特西

【BZOJ1821】[JSOI2010]部落划分（二分，并查集）

【BZOJ1821】[JSOI2010]部落划分（二分，并查集）

题面

题解

最新文章

热门文章