最小生成树——北极通讯网络

2023-05-16

问题 B: 北极通讯网络

时间限制: 1 Sec  内存限制: 128 MB
提交: 17  解决: 7
[提交][状态][讨论版][命题人:add_xiezhenghao]

题目描述

北极的某区域共有n座村庄(1≤n≤500),每座村庄的坐标用一对整数(x,y)表示,其中0≤x,y≤10000。为了加强联系,决定在村庄之间建立通讯网络。通讯工具可以是无线电收发机,也可以是卫星设备。所有的村庄都可以拥有一部无线电收发机, 且所有的无线电收发机型号相同。但卫星设备数量有限,只能给一部分村庄配备卫星设备。 

不同型号的无线电收发机有一个不同的参数d,两座村庄之间的距离如果不超过d就可以用该型号的无线电收发机直接通讯,d值越大的型号价格越贵。拥有卫星设备的两座村庄无论相距多远都可以直接通讯。

现在有k台(1≤k≤100)卫星设备,请你编写一个程序,计算出应该如何分配这k台卫星设备,才能使所有的无线电收发机的d值最小,并保证每两座村庄之间都可以直接或间接地通讯。

输入

第一行包括两个整数n、k,表示村庄的数量和卫星设备的数量。

之后的n行,输入xi,yi,表示第i个村庄的坐标。

输出

输出一个数,代表d的最小值。输出保留两位小数。

样例输入


3 2
10 10
10 0
30 0  

样例输出


10.00  

k个村庄装上卫星设备后可以看成1个点,那么只需要求这(n-k+1)个点和(n-k)条边所构成的最小生成树

利用Kruskal算法,只需要进行(n-k)次操作,最后一次操作时加入生成树的边的权值就是所求的d

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
int n,k,m,fa[505],x[505],y[505];
double d;
struct node//存储每条边的两个端点和距离
{
    int a,b;
    double distance;
}v[250000];
double dis(int ax,int ay,int bx,int by)//求两点之间距离
{
    return sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by));
}
int cmp(node n1,node n2)//按边的权值从小到大排序
{
    return n1.distance<n2.distance;
}
int getfather(int x)//求父亲节点,并查集
{
    if(fa[x]==x)return x;
    fa[x]=getfather(fa[x]);
    return fa[x];
}
void kruskal()//kruskal核心程序
{
   int f1,f2,num1=0;
   for(int i=1;i<=n;i++)//初始化每个点为一个集合
    fa[i]=i;
   for(int i=1;i<=m;i++)
   {
       f1=getfather(v[i].a);
       f2=getfather(v[i].b);
       if(f1!=f2)
       {
           fa[f1]=f2;//合并两个不同的集合
           num1++;
           if(num1==n-k)//放到第n-k条边
           {
               d=v[i].distance;//记录边的权值
               break;//退出
           }
       }
   }
}
int main()
{
    cin>>n>>k;
    if(k>=n)//每个村庄一台,d为0
    {
        cout<<"0.00"<<endl;
        return 0;
    }
    if(k==0)k=1;
    m=1;
    for(int i=1;i<=n;i++)//输入每个村庄的坐标
        cin>>x[i]>>y[i];
    for(int i=1;i<=n;i++)//求出每条边边权和端点,m记录边数
        for(int j=i+1;j<=n;j++)
        {
            v[m].a=i;
            v[m].b=j;
            v[m].distance=dis(x[i],y[i],x[j],y[j]);
            m++;
        }
    m--;
    sort(v+1,v+1+m,cmp);
    kruskal();
    cout.precision(2);
    cout<<fixed<<d<<endl;
    return 0;
}

 

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

最小生成树——北极通讯网络 的相关文章

  • Docker in docker 实现

    Docker in docker 文章目录 Docker in docker原理实现 xff08 centos7 xff09 常见问题参考 在docker容器内运行docker一般是不被倡导的 但有些场景和业务上 xff0c 需要在容器内使
  • 一篇文章入门spring

    Spring入门1 在之前我们对象的创建都是我们自己new出来的 xff0c 比如Student stu 61 new Student xff08 xff09 但是我们现在有了spring 我们将对象的创建的工作交给spring来处理 那么
  • JAVA数据结构之数组详细教程

    本文整理了java数据结构的数组操作 希望对刚入门数据结构的同志们有帮助 java数组非常简单 只要有JAVA语言基础就可以看这篇博文 大家不要害怕 非常简单 整理博客真的很花费时间 xff0c 如果对大家有帮助 xff0c 麻烦点赞评论
  • JAVA程序(MongoTemplate)操作mongodb数据库常用方法(超级详细)

    这里使用的是Spring 43 MongoTemplate来操作mongodb数据库 如果有不了解spring的同志先去了解一下spring为好 xff0c 这里给出实现的一些方法 主要有 xff1a 查询 增加 修改 删除 多字段增加 模
  • template操作mongodb数据库(更新方法大全)

    本文是使用JAVA程序操作MongoDB数据库 里面提供了各种更新数据的方法 xff0c 查询的各种方法会在后面进行更新 本文只是提供了数据库更新操作的一些方法 数据库数据和字段如下 xff1a 对于更新数据 xff0c 我将更新数据的方法
  • mongodb template 计算mongodb日期的解决方案

    mongodb由于特殊的日期格式 存在 8时区的问题 所以在使用java程序解决日期计算问题就会有点麻烦 其实也很简单 就是先将日期改变时区 然后转成带有格式String类型的日期 然后在java里面的将String转化成date类型即可
  • 一篇文章彻底理解二分搜索树(附代码实现)

    本文使用JAVA语言进行描述 其实本质上什么语言描述数据结构都是可以的 二叉树基础 二叉树的根节点 二叉树递归结构 xff1a 上面是一个满二叉树 但是实际中也有二叉树不是满的 二分搜索树 二分搜索树也不一定是满的 所以使用二分搜索树需要具
  • opengl 源码分析常见问题

    Opengl 一些问题解答 为什么opengl 不能跨线程 大家有没有想过这个问题 xff0c 网上给出的答案其实看得不太明白 xff0c 接下来我们看源码让你知道 C EGLContext Display createContext EG
  • mongodbtamplate使用程序创建mongdb索引的解决方案

    话不多说 xff0c 直接上代码 xff1a span class token keyword public span span class token keyword boolean span span class token funct
  • el表达式取不到值

    在jsp页面中有可能出现el表达式取不到值的问题 xff0c 但是反复检查代码 xff0c 跑断点都没有问题 xff0c 这是因为jsp忽略了el表达式 所以只要加上下面一行代码就可以了 span class token operator
  • Kaggle心脏病数据集为例学习机器学习的可解释性分析

    需要安装的工具包 pip install numpy pandas matplotlib seaborn wheel pandas profiling jupyter notebook span class token operator s
  • readlink /var/lib/docker/overlay2: invalid argument的解决方案

    发生这种情况是因为在运行Docker映像之间重新启动了docker xff0c 该映像已损坏 我重新启动系统 xff0c 然后运行以下命令 docker compose build no cache docker compose up 您还
  • python调用IP摄像头

    利用RTSP 43 opencv就可以实现网络摄像头的调用 rtsp是实时流传输协议 xff0c 是基于TCP IP协议体系中的一个应用层协议 xff0c 可以控制声音或者影像的多媒体串流协议 但是不同品牌的摄像头有不同的RTSP地址 下面
  • 22岁-时光如河,浮生为鱼

    时光如河 xff0c 浮生为 x1f41f 还没有学会告别 xff0c 四年就这样悄悄过去了 如往年今日一样 xff0c 依旧写些懒懒散散的文字致敬这一年的时光 x1f495 22岁生日快乐 x1f495 全文约4200字 xff0c 阅读
  • 电子书下载网站汇总

    网站名称地址简介语言推荐指数备注Book4Uhttp www book4you sk 外文下载网站斯洛伐克语 BookYardshttps www bookyards com en welcome主要面向教师的门户网站 xff0c 其中的书
  • Docker版 E5续订的E5调用API续订服务:Microsoft 365 E5 Renew X

    本文是基于作者SundayRX提出的E5 调用API续订服务 xff1a Microsoft 365 E5 Renew X的基础上提出的Docker版本的E5调用API续订服务 基础的账号注册等过程见SundayRX的博客 xff1a 账号
  • Docker版 Linux百度网盘备份工具

    一些必须要知道的事 xff1a 这个镜像的主要目的是为了将服务器或者群晖等linux场景中的资料备份到百度网盘中容器的基础镜像为ubuntu镜像 容器的备份周期为每天的凌晨两点 具体步骤如下 xff1a 下载镜像 docker pull h
  • 操作系统(五)中断和异常

    1 5 中断和异常 在上节内核态与用户态的转换过程中曾经提到过 xff0c 操作系统会响应中断信号强制夺回CPU使用权 xff0c 使用户态转换为内核态 中断 是操作系统夺回CPU使用权的唯一方式 xff0c 如果没有 中断 机制 xff0
  • Mediacodec 如何硬件解码到纹理的

    Mediacodec 如何硬件解码到纹理的 背景 xff1a 网上很多关于mediacodec xff0c surface xff0c surfacetexture的源码分析 xff0c 以及内部原理 xff0c 但是都局限于各自的内容 x
  • pyinstaller 递归深度设置(A RecursionError occurred)

    简介 xff1a pyinstaller常用于打包python文件 xff0c 当导入的包过多时常会出现一个递归深度超过限制的错误 这个可以通过设置最大递归深度来解决 1 pyinstaller报错信息 61 61 61 61 61 61

随机推荐

  • labelme标注格式转coco格式

    摘要 xff1a labelme是广泛使用的深度学习标注工具 xff0c 支持目标检测和实例分割等任务的标注 xff0c 但是一些框架如detectron2 xff0c solo等需要的是coco格式的 xff0c 这里提供一个示例把lab
  • opencv C++ 旋转任意角度图片

    摘要 xff1a opencv里面似乎没有直接的旋转图片的接口 xff0c 这里实现一个旋转任意角度的方法 xff0c 在旋转的时候调用opencv里面的仿射变换函数实现 有两种旋转模式 xff1a 一种按图片中心旋转 xff0c 尺寸与原
  • C++ opencv曲线拟合

    简介 xff1a 此问题是在做旋转模板匹配的时候 xff0c 选择最好的匹配结果时产生的 查找资料发现多项式拟合问题可以变成一个超定方程的求解问题 xff0c 而opencv中本身有一个cv solve 函数可以求解线性方程组 xff0c
  • C# 中的Bitmap 和(c++)opencv之间的传递

    C 中的Bitmap 和 xff08 c 43 43 xff09 opencv之间的传递 文章目录 C 中的Bitmap 和 xff08 c 43 43 xff09 opencv之间的传递1 C 传递bitmap给C 43 43 2 Pix
  • opencv kmeans (C++)

    kmeans 函数原型 span class token keyword double span cv span class token operator span span class token function kmeans span
  • C++ explict

    文章目录 C 43 43 中的explicit是一个关键字 xff0c 用于修饰构造函数 xff0c 它可以防止编译器进行隐式类型转换 xff0c 只允许显式地调用构造函数 它不能用于隐式转换和复制初始化 例如 xff0c 在下面的代码中
  • C++ friend

    在C 43 43 中 xff0c friend是一个关键字 xff0c 用于声明一个非成员函数或类可以访问另一个类的私有成员 例如 xff0c 我们有一个名为ClassA的类 xff1a span class token keyword c
  • C++ enum 和enum class

    文章目录 C 43 43 enum 和 enum class共同点区别 C 43 43 enum 和 enum class 在C 43 43 中 xff0c enum 是一种定义枚举类型的方法 一个枚举是一个整数值的命名集合 可以通过以下方
  • VS2019设置cl.exe环境变量

    版本 xff1a VS2019 设置 cl 环境变量 xff08 加入系统环境变量 xff08 PATH xff09 xff09 步骤 xff1a 1 找到cl exe的所在路径 xff0c 一般都在 xff1a C Program Fil
  • 从汇编角度看c++20 协程

    从汇编角度看c 43 43 20 协程 背景 xff1a 在学习c 43 43 20 协程的时候 xff0c 总对协程里边的局部成员存储 xff0c 以及协程栈恢复有很多疑问 xff0c 本次从过年arm64角度来分析下 xff0c 具体情
  • Win10 使用 Xrdp 远程控制 ubuntu16 闪退

    问题描述 win10使用 Xrdp 远程控制 ubuntu16 4 出现闪退 都能到这一步 xff0c 但是刚登上Xrdp4桌面就闪退 xff0c 回到下图 xfce4桌面xubuntu desktop xff0c 重新建立桌面会话 spa
  • 【华为OD机试真题 Java】字符串重新排列

    前言 本专栏将持续更新华为OD机试题目 并进行详细的分析与解答 包含完整的代码实现 希望可以帮助到正在努力的你 关于OD机试流程 面经 面试指导等 如有任何疑问 欢迎联系我 wechat steven moda email nansun09
  • atcoder abc140E (计算贡献)

    题目链接 大意 xff1a 让你 i 61 1 n
  • AtCoder Beginner Contest 143 E.Travel by Car(最短路)

    题目链接 大意 xff1a 给你一个无向带权图 xff0c 给你一些询问点 xff0c s t s t s t xff0c 你从s出发有 l
  • Ubuntu20.04软件安装大全

    目录 Ubuntu20 04 软件安装大全前言1 Windows和Ubuntu双系统安装1 1 下载Ubuntu系统镜像1 2 磁盘分区1 3 GPT分区安装Ubuntu1 4 系统完成后的一些设置1 5 遇到的一些小bug 2 换源2 1
  • 基于Nginx构建七牛云CDN静态资源加速

    创建七牛云账号 七牛云 进入管理控制台创建对象存储 3 配置nginx 使用nginx rewrite 的重定向功能进行转发到七牛云 server listen 80 server name test com 你的域名 location g
  • ChinaSkills-网络系统管理(2021年全国职业院校技能大赛A-1 模块 A:Linux 环境 真题 )

    前言 随着近年国家对技术性的比赛越来越重视 xff0c 各类技能大赛举办的相较正规 xff0c 这类大赛一般是在专科中专等技术性高中等院校中选拔优秀人才 xff0c 并且技能大赛的一等奖选手将有资格保送本科 xff0c 希望一些有能力的专科
  • Cannot resolve symbol 解决方案汇总(6种解决方案)

    Cannot resolve symbol 39 xxx 39 是比较常见一种错误 xff0c 以下整理常见的六种解决方案 xff0c 第六种会说明一下造成的原因和如何避免 方案一 检查一下pom文件依赖是否正常 xff0c 如不正常刷新m
  • 踩坑指南!import cv2出错怎么办?

    好久没有更新 xff0c 最近代码相关问题看的比较少 xff0c 有时候忙着debug就忘记了记录 xff0c 反思一下 背景 xff1a 在提取视频帧序列的时候用到了opencv包 xff0c 结果运行出错 解决 xff1a 经过查找资料
  • 最小生成树——北极通讯网络

    问题 B 北极通讯网络 时间限制 1 Sec 内存限制 128 MB 提交 17 解决 7 提交 状态 讨论版 命题人 add xiezhenghao 题目描述 北极的某区域共有n座村庄 xff08 1 n 500 xff09 xff0c