题解 P1991 【无线通讯网】
学无止境
2020-02-01 20:42:55
貌似大部分都是比较纯粹的最小生成树做法诶
这里 **并查集+二分答案** 的做法感觉也是很简明的
题目要我们求的**最小通话距离 $D$** 必须满足**每一对哨所之间至少有一条通话路径（直接的或者间接的）** 这个条件，因此我们可以设定精度要求来二分 $D$ ,并判定这个 $D$ 是否满足条件即可得到答案。
将哨所看成点，我们预处理出所有的边 $(i,j,k)$ 并根据 $k$ 排序 【$(i,j,k)$ 表示从点 $i$ 到点 $j$ 的边，边长为他们之间的距离 $k$ 】。
此时如果我们尝试判定一个 $D$ 是否满足条件,那么我们仅考虑长度小于等于 $D$ 的边，使用并查集维护连通性，我们可以计算出此时图中有多少个连通块。显然如果连通块数量如果大于 $1$ ，那么不同连通块之间就需要卫星电话来连接。若卫星电话数量 $s$ 大于等于连通块数量，那么就可以满足条件。
>注 ：对边排序的目的就是为了二分得到哪些边需要考虑。
设答案值域为 $V$ (本题 $V$ 最大为$10^8$) , 二分的时间复杂度为$O(log_2V)$ 。
判定是否满足条件的时间复杂度就是并查集(的时间复杂度这里我使用了路径压缩与按秩合并优化)，为 $O(pα(p))$
那么最终的时间复杂度就是 $O(pα(p)log_2V)$
代码里面有一些注释，可以结合理解。
>注 ： 这里 $α(p)$ 表示 $p$ 的反阿克曼函数值。
$Code:$
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
#define eps (0.0001)
//四舍五入，所以要保证前三位精确
struct edge
{
int u,v;
double w;
bool operator<(const edge q) const//运算符重载
{
return w<q.w;
}
}a[250010];
int s,p,tot,f[510],dep[510];
double pos[510][2],tmp[250010];
bool vis[510];//为了计算连通块数量添加的标记数组
inline double dis(int i,int j)//计算两点间距离
{
return sqrt((pos[i][0]-pos[j][0])*(pos[i][0]-pos[j][0])+(pos[i][1]-pos[j][1])*(pos[i][1]-pos[j][1]));
}
int getfa(int x)//实现并查集
{
if(f[x]==x)
return x;
return f[x]=getfa(f[x]);
}
inline bool check(double v)//判定是否满足条件
{
int bound=(upper_bound(tmp+1,tmp+1+tot,v)-tmp)-1,cnt=0;//1~bound 就是需要考虑的边了; cnt为连通块计数器
memset(vis,0,sizeof(vis));
for(register int i=1;i<=p;i++)//并查集初始化
f[i]=i,dep[i]=1;
for(register int i=1;i<=bound;i++)//并查集维护连通性
{
int x=a[i].u,y=a[i].v;
int fx=getfa(x),fy=getfa(y);
if(fx!=fy)
{
if(dep[fx]>dep[fy])
f[fy]=fx;
else if(dep[fx]<dep[fy])
f[fx]=fy;
else
f[fy]=fx,dep[fx]++;
}
}
for(register int i=1;i<=p;i++)//计算连通块数量
{
int temp=getfa(i);
if(!vis[temp])
vis[temp]=true,cnt++;
}
if(cnt==1)//只有一个连通块则不需要考虑卫星电话
return true;
return (s>=cnt) ;//判断卫星电话够不够用
}
int main()
{
scanf("%d%d",&s,&p);
for(register int i=1;i<=p;i++)
scanf("%lf%lf",&pos[i][0],&pos[i][1]);
for(register int i=1;i<=p;i++)
for(register int j=i+1;j<=p;j++)
a[++tot].u=i,a[tot].v=j,a[tot].w=dis(i,j);
sort(a+1,a+1+tot);
for(register int i=1;i<=tot;i++)
tmp[i]=a[i].w;
double l=0.0,r=100000000.0,mid;
while((r-l)>eps)//二分答案
{
mid=(l+r)/2;
if(check(mid))
r=mid;
else
l=mid+eps;
}
printf("%.2lf",mid);
return 0;
}
```