题解 P4047 【[JSOI2010]部落划分】 并查集+二分答案

[到博客食用更加~~优雅~~优秀](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; } ```