https://loj.ac/problem/10065
题目描述
给出(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
",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
",v[i]);
printf("%.2lf",v[n-k]);
return 0;
}