欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - BZOJ1821
题意概括
平面上有n个点，现在把他们划分成k个部分，求不同部分之间最近距离的最大值。
两个部分的距离就是两个部分中的最近的点对的距离。
n<=1000
题解
我们把所有的点全部建边。
然后我们要更新答案，就要尽量弄掉短的边。
于是就按照kruscal那样从短的开始弄。
当然要用并查集。
最后答案就是剩余的有意义的边中最短的一条。
注意最后的处理，我由于这个wa了好多次。
代码
#include <cstring>#include <algorithm>#include <cstdio>#include <cstdlib>#include <cmath>using namespace std;const int N=1000+5,M=N*N;int n,k,fa[N];struct Point{int x,y;}p[N];int sqr(int x){return x*x;}struct Edge{int a,b,c;}e[M];bool cmp(Edge a,Edge b){return a.c<b.c;}int getf(int k){return fa[k]==k?k:fa[k]=getf(fa[k]);}int main(){scanf("%d%d",&n,&k);for (int i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y);int cnt=0;for (int i=1;i<=n;i++)for (int j=i+1;j<=n;j++){e[++cnt].a=i,e[cnt].b=j;e[cnt].c=sqr(p[i].x-p[j].x)+sqr(p[i].y-p[j].y);}sort(e+1,e+cnt+1,cmp);int tot=0;for (int i=1;i<=n;i++)fa[i]=i;int i;for (i=1;i<=cnt&&n-tot>k;i++){int a=e[i].a,b=e[i].b;if (getf(a)==getf(b))continue;fa[getf(a)]=getf(b);tot++;}for (;i<=cnt&&getf(e[i].a)==getf(e[i].b);i++);printf("%.2lf",sqrt(e[i].c));return 0;}
BZOJ1821 [JSOI2010]Group 部落划分 Group Kruscal
原文地址：http://www.cnblogs.com/zhouzhendong/p/7470813.html