1145. 北极通讯网络(Kruskal,并查集维护)
北极的某区域共有 n 座村庄,每座村庄的坐标用一对整数 (x,y) 表示。
为了加强联系,决定在村庄之间建立通讯网络,使每两座村庄之间都可以直接或间接通讯。
通讯工具可以是无线电收发机,也可以是卫星设备。
无线电收发机有多种不同型号,不同型号的无线电收发机有一个不同的参数 d,两座村庄之间的距离如果不超过 d,就可以用该型号的无线电收发机直接通讯,d 值越大的型号价格越贵。现在要先选择某一种型号的无线电收发机,然后统一给所有村庄配备,数量不限,但型号都是 相同的。
配备卫星设备的两座村庄无论相距多远都可以直接通讯,但卫星设备是 有限的,只能给一部分村庄配备。
现在有 k 台卫星设备,请你编一个程序,计算出应该如何分配这 k 台卫星设备,才能使所配备的无线电收发机的 d 值最小。
例如,对于下面三座村庄:

其中,|AB|=10,|BC|=20,|AC|=105√≈22.36
如果没有任何卫星设备或只有 1 台卫星设备 (k=0或 k=1),则满足条件的最小的 d=20,因为 A 和 B,B 和 C 可以用无线电直接通讯;而 A 和 C 可以用 B 中转实现间接通讯 (即消息从 A 传到 B,再从 B 传到 C);
如果有 2 台卫星设备 (k=2),则可以把这两台设备分别分配给 B 和 C ,这样最小的 d 可取 10,因为 A 和 B 之间可以用无线电直接通讯;B 和 C 之间可以用卫星直接通讯;A 和 C 可以用 B 中转实现间接通讯。
如果有 3 台卫星设备,则 A,B,C 两两之间都可以直接用卫星通讯,最小的 d 可取 0。
输入格式
第一行为由空格隔开的两个整数 n,k
接下来 n 行,每行两个整数,第 i 行的 xi,yi表示第 i 座村庄的坐标 (xi,yi)。
输出格式
一个实数,表示最小的 d 值,结果保留 2 位小数。
数据范围
1≤n≤500
0≤x,y≤104
0≤k≤100
输入样例:
3 2
10 10
10 0
30 0
输出样例:
10.00
| 难度:中等 |
| 时/空限制:1s / 64MB |
| 总通过数:5213 |
| 总尝试数:12579 |
| 来源:《信息学奥赛一本通》 , Waterloo University 2002 |
| 算法标签 |
解析 :
性质:建立一棵最小生成树,将最大的k个边去掉,剩下的边中的最大权值就是答案
具体操作:我们可以在使用Kruskal算法时记录一下连通分量的个数,当连通分量的个数<=k
时,此时图中最大的边的权值就是答案
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>using namespace std;
#define x first
#define y second
typedef long long LL;
const int N = 5e2 + 5,M=N*N/2;
typedef pair<int, int>PII;
int n, k;
struct e {int a, b;double c;
}e[M];
PII p[N];
int fa[N];double getdist(PII a, PII b) {double dx = a.first - b.first;double dy = a.second - b.second;return sqrt(fabs(dx * dx + dy * dy));
}int cmp(const struct e& a, const struct e& b) {return a.c < b.c;
}int find(int a) {if (fa[a] == a)return a;return fa[a] = find(fa[a]);
}int main() {cin >> n >> k;for (int i = 1; i <= n; i++) {scanf("%d%d", &p[i].x, &p[i].y);}int m = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j < i; j++) {e[++m] = { i,j,getdist(p[i],p[j])};}}for (int i = 1; i <= n; i++) {fa[i] = i;}sort(e + 1, e + 1 + m, cmp);int cnt = n;double maxd = 0;for (int i = 1; i <= m; i++) {if (cnt <= k) {break;}int a = find(e[i].a), b = find(e[i].b);double d = e[i].c;if (a != b) {fa[a] = b;cnt--;maxd = d;}}printf("%.2lf\n", maxd);return 0;
}
相关文章:
1145. 北极通讯网络(Kruskal,并查集维护)
北极的某区域共有 n 座村庄,每座村庄的坐标用一对整数 (x,y) 表示。 为了加强联系,决定在村庄之间建立通讯网络,使每两座村庄之间都可以直接或间接通讯。 通讯工具可以是无线电收发机,也可以是卫星设备。 无线电收发机有多种不…...
【23-24 秋学期】NNDL 作业9 RNN - SRN
简单循环网络(Simple Recurrent Network,SRN)只有一个隐藏层的神经网络. 目录 1. 实现SRN (1)使用Numpy (2)在1的基础上,增加激活函数tanh (3࿰…...
Docker + Jenkins + Nginx实现前端自动化部署
目录 前言一、前期准备工作1、示例环境2、安装docker3、安装Docker Compose4、安装Git5、安装Nginx和Jenkinsnginx.confdocker-compose.yml 6、启动环境7、验证Nginx8、验证Jenkins 二、Jenkins 自动化部署配置1、设置中文2、安装Publish Over SSH、NodeJS(1&#x…...
文生视频的发展史及其原理解析:从Gen2、Emu Video到PixelDance、SVD、Pika 1.0
前言 考虑到文生视频开始爆发,比如11月份就是文生视频最火爆的一个月 11月3日,Runway的Gen-2发布里程碑式更新,支持4K超逼真的清晰度作品(runway是Stable Diffusion最早版本的开发商,Stability AI则开发的SD后续版本)11月16日&a…...
【python+Excel】读取和存储测试数据完成接口自动化测试
http_request2.py用于发起http请求 #读取多条测试用例 #1、导入requests模块 import requests #从 class_12_19.do_excel1导入read_data函数 from do_excel2 import read_data from do_excel2 import write_data from do_excel2 import count_case #定义http请求函数COOKIENon…...
WordPress插件大全-免费的WordPress插件汇总
随着互联网的不断发展,网站建设变得日益普及。对于大多数人而言,WordPress是一个熟悉且易于使用的网站建设平台。然而,有时候我们可能会觉得WordPress的功能还不够满足我们的需求,这时候,插件就成了解决问题的得力工具…...
STM32通讯设计
STM32通讯设计 通讯流程STM32程序 通讯流程 1.使用HT2202芯片配置为主机接收(轮询模式)。 2.将STM32芯片配置为从机发送,中断模式下发送固定数据。 3.如果HT2202芯片能够收到STM32发送的数据则通讯成功,否则通讯失败。 STM32程序…...
外汇天眼:在QOINTEC投资需缴纳分成费才给出金?这合理么?
一般来说,在正规的平台上申请出金是不需要缴纳什么费用的,除非有一些特殊情况,像低额出金、没有交易就申请出金等情况下,或许会让你缴纳一定的手续费或者隔夜利息费等(不同的平台有不同的规则),…...
C_8练习题
一、单项选择题(本大题共20小题,每小题2分,共40分。在每小题给出的四个备选项中选出一个正确的答案,并将所选项前的字母填写在答题纸的相应位置上。) 1,在每个C语言程序中都必须包含有这样一个函数,该函数的函数名为() A. main B. MAIN C.name D. function 以下正确…...
HuggingFace学习笔记--Tokenizer的使用
1--AutoTokenizer的使用 官方文档 AutoTokenizer() 常用于分词,其可调用现成的模型来对输入句子进行分词。 1-1--简单Demo 测试代码: # 分词器测试Demo from transformers import AutoTokenizerif __name__ "__main__":checkpoint "…...
解决苹果手机iphone手机强制重启
强制关机: 方法1.同时按住左侧的,- 键中的一个和右侧的电源键 方法2.点击桌面的悬浮键–设备–更多–重新启动...
10分钟的时间,带你彻底搞懂JavaScript数据类型转换
前言 📫 大家好,我是南木元元,热衷分享有趣实用的文章,希望大家多多支持,一起进步! 🍅 个人主页:南木元元 目录 JS数据类型 3种转换类型 ToBoolean ToString ToNumber 对象转原…...
好用的chatgpt工具用过这个比较快
chatgpthttps://www.askchat.ai?r237422 chatGPT能做什么 1. 对话和聊天:我可以与您进行对话和聊天,回答您的问题、提供信息和建议。 2. 问题回答:无论是关于事实、历史、科学、文化、地理还是其他领域的问题,我都可以尽力回答…...
系统设计概念:生产 Web 应用的架构
在你使用的每个完美应用程序背后,都有一整套的架构、测试、监控和安全措施。今天,让我们来看看一个生产就绪应用程序的非常高层次的架构。 CI/CD 管道 我们的第一个关键领域是持续集成和持续部署——CI/CD 管道。 这确保我们的代码从存储库经过一系列测试…...
基于docker的onlyoffice使用--运行JavaSpringExample
背景 我之前看到有开源项目很好地集成了onlyoffice,效果要比kkfilepreview好(应当说应用场景不太一样)。本文是在window10环境,安装完Docker Desktop的基础上运行onlyoffice,并利用官网JavaSpringExample进行了集成。 …...
SQL server-excel数据追加到表
参考文章:SQL server 2019 从Excel导入数据_mssql2019 导入excel数据-CSDN博客 将excel数据导入到SQL server数据库的详细过程 注意:第一行数据默认为数据库表中的字段,所以这个必须要有,否则无法映射导入 问题1:ADD…...
深度学习-模型调试经验总结
1、 这句话的意思是:期望张量的后端处理是在cpu上,但是实际是在cuda上。排查代码发现,数据还在cpu上,但是模型已经转到cuda上,所以可以通过把数据转到cuda上解决。 解决代码: tensor.to("cuda")…...
Redis打包事务,分批提交
一、需求背景 接手一个老项目,在项目启动的时候,需要将xxx省整个省的所有区域数据数据、以及系统字典配置逐条保存在Redis缓存里面,这样查询的时候会更快; 区域数据字典数据一共大概20000多条,,前同事直接使用 list.forEach…...
深度学习毕设项目 深度学习 python opencv 动物识别与检测
文章目录 0 前言1 深度学习实现动物识别与检测2 卷积神经网络2.1卷积层2.2 池化层2.3 激活函数2.4 全连接层2.5 使用tensorflow中keras模块实现卷积神经网络 3 YOLOV53.1 网络架构图3.2 输入端3.3 基准网络3.4 Neck网络3.5 Head输出层 4 数据集准备4.1 数据标注简介4.2 数据保存…...
leetcode 611. 有效三角形的个数(优质解法)
代码: class Solution {public int triangleNumber(int[] nums) {Arrays.sort(nums);int lengthnums.length;int n0; //三元组的个数//c 代表三角形最长的那条边for (int clength-1;c>2;c--){int left0;int rightc-1;while (left<right){if(nums[left]nums[r…...
多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...
使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
C++实现分布式网络通信框架RPC(2)——rpc发布端
有了上篇文章的项目的基本知识的了解,现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...
若依登录用户名和密码加密
/*** 获取公钥:前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...
