题目描述
给出n个村庄的位置，求如何选取k个村庄使得最大的d值最小。
思路
正向思维比较复杂，我们考虑逆向思维，当最大的d值为多少时恰好需要k个卫星设备。这样就转化为将可以用无线电通信的村庄连边，图中有k个连通支。或者说将图中所有村庄两两连边，去掉大于d的边后图中有k个连通支。
定理：如果去掉所有权值大于d的边后，最小生成树被分割为k个连通支，则图也被分割为k个连通支。
证明：假设原图被分为cnt个连通支（cnt！=k），显然只可能cnt<k。那么在图的一个连通支中必定被分为2部分，设为T1，T2，并且在原图中有边相连，而在最小生成树中有一条连接被断开，因此在原图中有一条连接T1、T2的边而小于最小生成树中连接T1、T2的边，那么可以将这条边加入最小生成树，得到一棵更小的生成树，显然不成立，由此定理成立。
而要将最小生成树恰好分成k个连通支，d值即为最小生成树中的第k长边。我们考虑Kruskal的过程，每次选出一条连接两个未连通的连通支的边，因此每一条边都连通着两个连通支，所以删去k条边就形成k个连通支。
代码
#include <bits/stdc++.h> using namespace std; struct aa { int u,v; double w; }a[250005]; struct Node { int x,y; }p[600]; int fa[600]; double v[600]; int sqr(int x) { return x*x; } bool cmp(aa x,aa y) { return x.w<y.w; } int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); } int main() { int n,k; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d%d",&p[i].x,&p[i].y); fa[i]=i; } int cnt=0; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(i^j) { a[++cnt].u=i;a[cnt].v=j; a[cnt].w=sqrt(sqr(p[i].x-p[j].x)+sqr(p[i].y-p[j].y)); } sort(a+1,a+cnt+1,cmp); // for(int i=1;i<=cnt;i++) // printf("%.2lf\n",a[i].w); int j=0; for(int i=1;i<=cnt;i++) { int fx=find(a[i].u),fy=find(a[i].v); if(fx!=fy) { fa[fx]=fy; v[++j]=a[i].w; if(j==n-1)break ; } } // for(int i=1;i<n;i++) // printf("%.2lf\n",v[i]); printf("%.2lf",v[n-k]); return 0; }