题解 P4047 【[JSOI2010]部落划分】 并查集+二分答案
wjyyy
2018-07-05 19:33:49
[到博客食用更加~~优雅~~优秀](http://www.wjyyy.top/735.html)
## 解法:
我的第一思路是**二分答案**检验,把某个距离以内的划分为同一个部落,检查是否被划分为k个部落。如果超过k个,则范围扩大,如果不超过k个(含k个),则范围缩小。因为题目要求分出k个部落,**使两两部落间最小的距离最大**。而同时,当部落多了应当控制距离增大,当部落少了控制距离减小。因此是有**单调性**的。~~(一开始并查集写错只有70分吓得我打了好长时间的对拍)~~
### 二分答案过程:
检查以mid为距离,枚举各个点,与点i的距离比mid小的,则与i归为一个部落。因为部落的基准点不同,也就是一个点可以因为**存在部落里一个点与之距离小于mid**而被归为一个部落。因为把各个点拉进同一个部落的点可能不同,因此我们可以用并查集做到这一点。被归为一个部落的用并查集放在一起就可以了。
#### 其他
题解里其他同学做的是用生成树来做的,就是把所有点两两互连,当做一个有$\frac{n(n-1)}2$条边的稠密图,来做最小生成树,每**拉**一个点进来就减少一个连通块,最后一个使得连通块个数减为k的边即为所求。这样在某些情况会比二分答案更优,但在稠密图用二分答案比用kruscal在时间和空间上都稍微优一些 :) 。不过比较难想,细节颇多。
**tips:二分平方最后开根可能精度更有保证,这个题保留2位小数就无所谓了&& 发现题目图片原来有彩蛋『JSOI』啊**
## Code:
```cpp
#include<cstdio>
#include<cstring>
#include<cmath>
#define eps 1e-4
int c[10100],n,m;
int x[1010],y[1010];
int my_find(int x)
{
if(c[x]==x)
return x;
return c[x]=my_find(c[x]);
}
bool check(double ans)
{
for(int i=1;i<=n;i++)
c[i]=i;
int cnt=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if((x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i])<=ans)//暂时不开根号
c[my_find(i)]=my_find(j);
for(int i=1;i<=n;i++)
if(my_find(i)==i)
cnt++;
if(cnt<m)//框多了
return false;
return true;
}
int main()
{
double mx=0.0,my=0.0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&x[i],&y[i]);
mx=mx>x[i]?mx:x[i];//减小二分上界(其实没必要)
my=my>y[i]?my:y[i];
}
//二分平方,保证精度(其实也没必要)
double l=0.0,r=mx*mx+my*my,mid;
while(r-l>eps)
{
mid=(l+r)/2.0;
if(check(mid))
l=mid;
else
r=mid;
}
printf("%.2lf\n",sqrt(l));
return 0;
}
```