要求用尽可能小的代价使图联通，考虑最小生成树。如果不断加边，将分散的点连结为\(p-s\)个联通块，则\(s\)个无线电站可以分布在每个联通块中的任意点。
而此处要求的半径D是对于所有点的覆盖半径，相当于最小瓶颈生成树。使用kruskal连边，答案就是连的\(p-s\)条边中最长的一条。
代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
struct ne
{
int from,to;
double dis;
}ng[400005];//两个点，权值表示法
struct point
{
int x,y;
}ps[105];
int head[5005],dis[5005],f[400005];
int s,p,eg,cnt;
double ans;
bool vis[5005];
inline void merge(int n1,int n2)
{
f[n1]=n2;
}
inline int find(int num)
{
if(num==f[num]) return num;
return f[num]=find(f[num]);
}
inline bool comp(ne e1,ne e2)
{
return e1.dis<e2.dis;
}
double MST()
{
sort(ng+1,ng+1+eg,comp);
for(int i=1;i<=p;i++)
f[i]=i;
for(int i=1;i<=eg;i++)
{
if(find(ng[i].from)==find(ng[i].to))
continue;
ans=ng[i].dis;
f[find(ng[i].from)]=find(ng[i].to);
if(++cnt==p-s) break;
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin>>s>>p;
for(int i=1;i<=p;i++)
{
cin>>ps[i].x>>ps[i].y;
//cin>>ng[i].from>>ng[i].to>>ng[i].dis;
}
for(int i=1;i<=p;i++)
for(int j=1;j<i;j++)
{
ng[++eg].from=i;
ng[eg].to=j;
ng[eg].dis=sqrt((ps[i].x-ps[j].x)*(ps[i].x-ps[j].x)+(ps[i].y-ps[j].y)*(ps[i].y-ps[j].y));
}
printf("%.2lf",MST());
return 0;
}
转载于:https://www.cnblogs.com/ehznehc/p/11484490.html
