P1991 无线通讯网

    • 1.7K通过
    • 4.2K提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 图论 并查集 生成树 邻接矩阵
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    国防部计划用无线网络连接若干个边防哨所。2 种不同的通讯技术用来搭建无线网络;

    每个边防哨所都要配备无线电收发器;有一些哨所还可以增配卫星电话。

    任意两个配备了一条卫星电话线路的哨所(两边都ᤕ有卫星电话)均可以通话,无论

    他们相距多远。而只通过无线电收发器通话的哨所之间的距离不能超过 D,这是受收发器

    的功率限制。收发器的功率越高,通话距离 D 会更远,但同时价格也会更贵。

    收发器需要统一购买和安装,所以全部哨所只能选择安装一种型号的收发器。换句话

    说,每一对哨所之间的通话距离都是同一个 D。你的任务是确定收发器必须的最小通话距

    离 D,使得每一对哨所之间至少有一条通话路径(直接的或者间接的)。

    输入输出格式

    输入格式:

    从 wireless.in 中输入数据第 1 行,2 个整数 S 和 P,S 表示可安装的卫星电话的哨所

    数,P 表示边防哨所的数量。接下里 P 行,每行两个整数 x,y 描述一个哨所的平面坐标

    (x, y),以 km 为单位。

    输出格式:

    输出 wireless.out 中

    第 1 行,1 个实数 D,表示无线电收发器的最小传输距离,㋮确到小数点后两位。

    输入输出样例

    输入样例#1: 复制
    2 4
    0 100
    0 300
    0 600
    150 750
    
    输出样例#1: 复制
    212.13
    

    说明

    附送样例一个

    对于 20% 的数据:P = 2,S = 1

    对于另外 20% 的数据:P = 4,S = 2

    对于 100% 的数据保证:1 ≤ S ≤ 100,S < P ≤ 500,0 ≤ x,y ≤ 10000。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。