【JSOI2010】【BZOJ1821】部落划分(二分+并查集)
显然最近的两个部落的距离是有单调性的 因此可以二分
考虑check 我们遍历所有点 先把<=limit的点连起来 这样是肯定可以划分在一个部落里的 再用并查集维护一下
然后扫一遍 如果father[i]=i 说明就有一个部落
注意double
#include<bits/stdc++.h>
#define N 1005
#define eps 1e-6
using namespace std;
template<class T>
inline void read(T &x)
{
x=0;
static char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
}
int n,k;
double dis[N][N];
struct P
{
double x,y;
}point[N];
inline double calc_dis(int i,int j)
{
return sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y));
}
int father[N];
inline int getfather(int x)
{
if(father[x]==x) return x;
father[x]=getfather(father[x]);
return father[x];
}
inline bool check(double limit)
{
for(int i=1;i<=n;i++) father[i]=i;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(dis[i][j]>limit) continue;
int fa1=getfather(i),fa2=getfather(j);
if(fa1!=fa2) father[fa1]=fa2;
}
}
int ans=0;
for(int i=1;i<=n;i++)
if(father[i]==i) ans++;
return ans>=k;
}
int main()
{
read(n); read(k);
for(int i=1;i<=n;i++) read(point[i].x), read(point[i].y);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=calc_dis(i,j);
double l=0,r=100000;
while(l+eps<=r)
{
double m=(l+r)/2;
if(check(m)) l=m;
else r=m;
}
cout<<fixed<<setprecision(2)<<l;
return 0;
}
转载于:https://www.cnblogs.com/Patrickpwq/articles/9847659.html