題意：
給你N<=1000個平面上的點 讓你將這些點劃分為K<=N個部分，使得最靠近的兩個部落盡量遠離。
做法：
這個題初看好像沒什么思路 所以我們要發(fā)掘它的本質(zhì)
本題等價于將初始N個連通塊通過N-K次有效合并成K個連通塊，使得剩下的連接兩個不同連通塊的最小邊最大。
恰恰Kruskal算法的目標便是通過合并得到1個連通塊，使最大的邊最小，即剩下的最小邊最小。
考慮這兩者的聯(lián)系，我們可以設計這樣一個算法：
我們用Kruskal的做法，并查集合并N-K+1次時，這條邊便是答案。
簡單地不嚴謹?shù)刈C明一下這個是最優(yōu)解：
對于已經(jīng)生成的劃分邊集E， 其中有N-K條有效合并邊
我們用一條不在E集合中的邊去替換E集合中的邊 這兩條邊必然是同一個性質(zhì)的
1.一條可合并邊替換了一條有效合并邊：剩下的連接不同連通塊的最小邊成為了換出來的邊 不可行
2.一條非可合并邊替換一條非有效合并邊：對原來的解不產(chǎn)生變化
所以這樣就可以解決了此題
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