题意：
给你N<=1000个平面上的点 让你将这些点划分为K<=N个部分，使得最靠近的两个部落尽量远离。
做法：
这个题初看好像没什么思路 所以我们要发掘它的本质
本题等价于将初始N个连通块通过N-K次有效合并成K个连通块，使得剩下的连接两个不同连通块的最小边最大。
恰恰Kruskal算法的目标便是通过合并得到1个连通块，使最大的边最小，即剩下的最小边最小。
考虑这两者的联系，我们可以设计这样一个算法：
我们用Kruskal的做法，并查集合并N-K+1次时，这条边便是答案。
简单地不严谨地证明一下这个是最优解：
对于已经生成的划分边集E， 其中有N-K条有效合并边
我们用一条不在E集合中的边去替换E集合中的边 这两条边必然是同一个性质的
1.一条可合并边替换了一条有效合并边：剩下的连接不同连通块的最小边成为了换出来的边 不可行
2.一条非可合并边替换一条非有效合并边：对原来的解不产生变化
所以这样就可以解决了此题
1 #include <cstdio>
2 #include <cmath>
3 #include <algorithm>
4 using namespace std;
5 struct TEdge
6 {
7 int w,x,y;
8 } e[1000005];
9 int Ance[1005],X[1005],Y[1005],N,K,E;
10 inline TEdge TEdge_make(int w,int x,int y)
11 {
12 TEdge ret;
13 ret.w=w,ret.x=x,ret.y=y;
14 return ret;
15 }
16 inline int GetAnce(int x)
17 {
18 int p=x,q=x,k=Ance[x];
19 for (;p!=Ance[p];p=Ance[p]);
20 for (;q!=p;Ance[q]=p,q=k,k=Ance[q]);
21 return p;
22 }
23 inline bool cmp(const TEdge &a,const TEdge &b)
24 {
25 return a.w<b.w;
26 }
27 int main()
28 {
29 freopen("group.in","r",stdin);
30 freopen("group.out","w",stdout);
31 scanf("%d%d",&N,&K);
32 for (int i=1;i<=N;++i)
33 scanf("%d%d",&X[i],&Y[i]);
34 for (int i=1;i<N;++i)
35 for (int j=i+1;j<=N;++j)
36 e[++E]=TEdge_make((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]),i,j);
37 sort(e+1,e+E+1,cmp);
38 for (int i=1;i<=N;++i)
39 Ance[i]=i;
40 for (int i=1,cnt=N;i<=E;++i)
41 {
42 int u=GetAnce(e[i].x),v=GetAnce(e[i].y);
43 if (u!=v)
44 {
45 Ance[u]=v;
46 if (--cnt==K-1) return printf("%.2lf\n",sqrt((double)e[i].w)),0;
47 }
48 }
49 return 0;
50 }
51