题目
BZOJ 1821: [JSOI2010]Group 部落划分 Group
分析
竟然是一道kruskal……好久都没有看出来。
首先各点之间两两连边构建一张完全图，模拟kruskal从小到大加边；
设初始有n个部落，即每个点各自为一个部落，每加一条边，相当于减少一个部落；
恰好有k个部落时，当前要加上的那条边即为当前最近的两部落间的距离；
由于前面加入的边都不长于当前边，所以当前边就是所有部落中的最远距离，也就是答案。
因此每加一条边可以让部落数-1；
当部落数减为k时输出当前边权，否则继续加边。
代码
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=1002;
struct Edge{int from,to;double v;bool operator < (const Edge &A) const{return v<A.v;}
}e[maxn*maxn];
int x[maxn],y[maxn],fa[maxn];
int n,k,ans,cnt;void add(int i,int j)
{double w=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));e[++cnt].from=i;e[cnt].to=j;e[cnt].v=w;
}int Find(int x)
{if(fa[x]==x) return x;return fa[x]=Find(fa[x]);
}void Union(int x,int y)
{fa[Find(y)]=Find(x);
}bool judge(int x,int y)
{return Find(x)==Find(y);
}int main()
{scanf("%d%d",&n,&k);for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]),fa[i]=i;for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)add(i,j),add(j,i);sort(e+1,e+cnt+1);for(int i=1;i<=cnt;i++){int u=e[i].from,v=e[i].to;if(judge(u,v)) continue;if(n>k){n--;Union(u,v);}else{printf("%.2lf",e[i].v);return 0;}}return 0;
}