P1991 无线通讯网
2018-06-17 22:23:35来源:未知 阅读 ()
题目描述
国防部计划用无线网络连接若干个边防哨所。2 种不同的通讯技术用来搭建无线网络;
每个边防哨所都要配备无线电收发器;有一些哨所还可以增配卫星电话。
任意两个配备了一条卫星电话线路的哨所(两边都?有卫星电话)均可以通话,无论
他们相距多远。而只通过无线电收发器通话的哨所之间的距离不能超过 D,这是受收发器
的功率限制。收发器的功率越高,通话距离 D 会更远,但同时价格也会更贵。
收发器需要统一购买和安装,所以全部哨所只能选择安装一种型号的收发器。换句话
说,每一对哨所之间的通话距离都是同一个 D。你的任务是确定收发器必须的最小通话距
离 D,使得每一对哨所之间至少有一条通话路径(直接的或者间接的)。
输入输出格式
输入格式:从 wireless.in 中输入数据第 1 行,2 个整数 S 和 P,S 表示可安装的卫星电话的哨所
数,P 表示边防哨所的数量。接下里 P 行,每行两个整数 x,y 描述一个哨所的平面坐标
(x, y),以 km 为单位。
输出格式:输出 wireless.out 中
第 1 行,1 个实数 D,表示无线电收发器的最小传输距离,?确到小数点后两位。
输入输出样例
2 4 0 100 0 300 0 600 150 750
212.13
说明
附送样例一个
对于 20% 的数据:P = 2,S = 1
对于另外 20% 的数据:P = 4,S = 2
对于 100% 的数据保证:1 ≤ S ≤ 100,S < P ≤ 500,0 ≤ x,y ≤ 10000。
预处理距离,
然后跑kruskal
一开始以为自己数组开小了。。
结果仔细检查了一下才发现是kruskal写错了一个地方
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<cstdlib> 6 #include<algorithm> 7 using namespace std; 8 const int MAXN=1000001; 9 void read(int & n) 10 { 11 char c='+';int x=0; 12 while(c<'0'||c>'9')c=getchar(); 13 while(c>='0'&&c<='9') 14 x=x*10+(c-48),c=getchar(); 15 n=x; 16 } 17 int p,n; 18 double far[1001][1001]; 19 int heng[MAXN],zong[MAXN]; 20 void calc() 21 { 22 for(int i=1;i<=n;i++) 23 for(int j=1;j<=n;j++) 24 { 25 if(i==j) 26 far[i][j]=0; 27 else 28 far[i][j]=(double)sqrt((double)(abs(heng[i]-heng[j])*abs(heng[i]-heng[j]))+(double)(abs(zong[i]-zong[j])*abs(zong[i]-zong[j]))); 29 } 30 } 31 32 struct node 33 { 34 int u,v; 35 double w; 36 }edge[1000001]; 37 int num=1; 38 void add_edge(int x,int y,double z) 39 { 40 edge[num].u=x; 41 edge[num].v=y; 42 edge[num].w=z; 43 num++; 44 } 45 int comp(const node & a ,const node & b) 46 { 47 return a.w<b.w; 48 } 49 int fa[1000001]; 50 int find(int x) 51 { 52 if(fa[x]==x) 53 return fa[x]; 54 return fa[x]=find(fa[x]); 55 } 56 void unionn(int x,int y) 57 { 58 int fx=find(x); 59 int fy=find(y); 60 fa[fx]=fy; 61 } 62 void kruskal() 63 { 64 int tot=0;double ans=-1; 65 sort(edge+1,edge+num,comp); 66 for(int i=1;i<=num-1;i++) 67 { 68 if(edge[i].u!=0&&edge[i].v!=0&&find(edge[i].u)!=find(edge[i].v)) 69 { 70 unionn(edge[i].u,edge[i].v); 71 tot++; 72 ans=max(ans,edge[i].w); 73 } 74 if(tot==n-p) 75 break; 76 } 77 printf("%.2lf",ans); 78 } 79 int main() 80 { 81 read(p);read(n); 82 for(int i=0;i<=n;i++) 83 fa[i]=i; 84 for(int i=1;i<=n;i++) 85 { 86 read(heng[i]); 87 read(zong[i]); 88 } 89 calc(); 90 for(int i=1;i<=n;i++) 91 for(int j=1;j<=n;j++) 92 add_edge(i,j,far[i][j]); 93 kruskal(); 94 return 0; 95 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:P1086 花生采摘
下一篇:P1032 字串变换
- 洛谷 P1991 无线通讯网 2019-09-08
- P2038 无线网络发射器选址 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash