AcWing 1145. 北极通讯网络
原题链接
中等
作者:
ZTEG
,
2019-11-26 09:59:52
,
所有人可见
,
阅读 1244
k个村庄装上卫星设备后可以看成1个点,那么只需要求这(n-k+1)个点和(n-k)条边所构成的最小生成树
利用Kruskal算法,只需要进行(n-k)次操作,最后一次操作时加入生成树的边的权值就是所求的d
#include<bits/stdc++.h>
using namespace std;
long long x[600];
long long y[600];
long long fa[600];
struct oppo{
long long from,to;
double s;
}rood[400000];
long long tot;
long long n,k;
long long now;
double ans;
double jl(long long a,long long b)
{
return sqrt((double)(x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
bool rule(oppo a,oppo b)
{
return a.s<b.s;
}
long long find(long long x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);//返回和路径压缩
}
int main()
{
cin>>n>>k;
for(long long i=1;i<=n;i++)
scanf("%lld %lld",&x[i],&y[i]);
for(long long i=1;i<n;i++)
for(long long j=i+1;j<=n;j++)
{
rood[++tot].from=i;
rood[tot].to=j;
rood[tot].s=jl(i,j);
}
sort(rood+1,rood+tot+1,rule);
for(long long i=1;i<=n;i++)
fa[i]=i;
for(long long i=1;i<=tot;i++)
{
long long a=find(rood[i].from);
long long b=find(rood[i].to);
if(a!=b)
{
fa[b]=a;
ans=rood[i].s;
now++;
}
if(now==n-k)
break;
}
printf("%.2lf\n",ans);
return 0;
}