洛谷 P1991 无线通讯网
程序员文章站
2023-11-14 17:18:34
[TOC] 题目 "P1991 无线通讯网" 题目大意 我一开始在题意上理解有问题先说一下题意。你要让$p$个哨所都可以互相通话(可以是间接),可以通过 也可以通过 。这个 它特别流啤,没有距离限制,只要两个哨所都有 就可以通话而 有一定的距离限制,只有两个哨所之间的距离小于$D$才可以通话。现在给 ......
目录
题目
题目大意
我一开始在题意上理解有问题先说一下题意。你要让$p$个哨所都可以互相通话(可以是间接),可以通过无线电收发器
也可以通过卫星电话
。这个卫星电话
它特别流啤,没有距离限制,只要两个哨所都有卫星电话
就可以通话而无线电收发器
有一定的距离限制,只有两个哨所之间的距离小于$d$才可以通话。现在给你$s$个卫星电话
,让你将着$s$个电话分配一下,使得最后$d$最小。(可能描述的也不好,见谅。。。)
思路
并查集。算出没两个哨所之间的距离存起来,按距离由小到大排序,再由小到大枚举这些边,如果边连接的两个哨所不在同一个联通块内就连起来,连通块数量减一(一开始连通块数量为$p$),直到连通块数量为$s$(剩下的不连通的用卫星电话
),因为$s$个卫星电话
可以免费连接$s-1$个哨所,所以只要连通块数量为$s$就可以停止了。
$code$
#include<iostream> #include<cstring> #include<cstdio> #include<iomanip> #include<algorithm> #include<string> #include<cmath> #define maxn 501 int s,p,fa[maxn],size[maxn]; int a[maxn],b[maxn]; struct info{ int u,v; double w; }qwq[250001]; bool cmp(info a,info b){ return a.w<b.w; } int find(int x){ return fa[x]==x?x:fa[x]=find(fa[x]); } void union(int x,int y){ int rootx=find(x),rooty=find(y); if(rootx==rooty) return; if(size[rootx]>size[rooty]){ fa[rooty]=rootx; size[rootx]+=size[rooty]; }else{ fa[rootx]=rooty; size[rooty]+=size[rootx]; } } inline void read(int &t){ int x=0;bool f=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} t=f?-x:x; } int main(){ read(s),read(p); for(int i=1;i<=p;++i) fa[i]=i; for(int i=1;i<=p;++i) read(a[i]),read(b[i]); int sum=0; for(int i=1;i<=p;++i){ for(int j=1;j<=p;++j){ if(i!=j){ double jl=sqrt((a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j])); sum++; qwq[sum].u=i,qwq[sum].v=j,qwq[sum].w=jl; } } } std::sort(qwq+1,qwq+sum+1,cmp); int stop=1+(s-1); int ub=p; for(int i=1;i<=sum;++i){ if(ub==stop){ std::cout<<std::fixed<<std::setprecision(2)<<qwq[i-1].w; return 0; } if(find(qwq[i].u)!=find(qwq[i].v)){ union(qwq[i].u,qwq[i].v); ub--; } } return 0; }