生成树(习题)
模板】最小生成树
生成树有两种方法,但是我只会克鲁斯卡尔算法,所以接下来下面的的题目都是按照这个算法来实现的,首先来见一下生么是这个算法,在之前的我写的一篇博客中有题使叫修复公路,其实这一题就是使用了这个算法:用一个结构体记录两个区域的编号,和着两条区域之间道路的价值,再利用sort(排序函数)按照从小到大进行排序(有些题目要按照从大到小进行排序),利用并查集将各个区域进链接,直到所有区域都链接起来(假设有n个区域,那么这个算法要求只能有n-1条边构成)。好了讲完了这个算法的原理就很容易实现了,
首先就是并查集的模板,查和并的操作。
int cha(int x)
{return fa[x] == x ? x : fa[x] = cha(fa[x]);
}void Union(int x, int y)
{x = cha(x);y = cha(y);if (x == y) return;if(x!=y){fa[x] = y;
// cot--;}
}
在是构建主函数
int main()
{cin>>n>>m;for(int i=1;i<=m;i++){fa[i]=i;}for(int i=1;i<=m;i++){cin>>q[i].x>>q[i].y>>q[i].t;}sort(q+1,q+1+m,cmp);for(int i=1;i<=m;i++){bing(q[i].x,q[i].y,i);// sum+=q[i].t;if(n==1){cout<<sum<<endl;return 0;}}cout<<"orz"<<endl;return 0;
}
需要注意的是当我们将各个链接成一个整体的时候(即原来有n个整体,后来通过并查集进行链接成一个整体后n就变为1了,这是我们退出的条件)只需要再并函数中设置条件即可(即如果通过查发现这两个节点的根节点不相同,就说明了还没有并在一起,那么就需要将这两区域并在一起,那么整体的数量就变为n-1了)。
完整代码如下:
#include<iostream>
#include<algorithm>
#define N 1002000
#define ll long long
//#define inf 0x7fffffff
using namespace std;
int fa[N];
int n,m;
ll sum=0;struct node
{int x,y,t;
}q[N];int cha(int x)
{return fa[x]==x?fa[x]:fa[x]=cha(fa[x]);
}void bing(int x,int y,int i)
{x=cha(x);y=cha(y);if(x==y)return ;else{fa[x]=y;sum+=q[i].t;//这个一点更要放在这个函数里面不然会导致会有多余的数多进行了计算n--;}
}bool cmp(node x,node y)
{return x.t<y.t;
}int main()
{cin>>n>>m;for(int i=1;i<=m;i++){fa[i]=i;}for(int i=1;i<=m;i++){cin>>q[i].x>>q[i].y>>q[i].t;}sort(q+1,q+1+m,cmp);for(int i=1;i<=m;i++){bing(q[i].x,q[i].y,i);// sum+=q[i].t;if(n==1){cout<<sum<<endl;return 0;}}cout<<"orz"<<endl;return 0;
}
P1991 无线通讯网

这一题确实算比较难以理解,我也是看了题解和想了很才明白一点,首先我们需要知道的就是这个s究竟是用来干啥的,首先我们需要知道当两个地方都安装了卫星就代表着这两个地方就不再收到距离的影响,那么为了使这个距离尽量的短,所以我们就需要将某两个距离尽量的大的地方安装卫星,所以我们就要使用一个结构体数组将两地的编号和距离储存起来,对于如何将这两个地方的编号和距离储存起来就需要用到一个嵌套循环
代码如下
for (int i = 1; i <= p; i++){for (int j = i + 1; j <= p; j++){cnt++;q[cnt].x = i;//这一步和下一行都是为了存编号q[cnt].y = j;q[cnt].z = sqrt((a[i] - a[j]) * (a[i] - a[j]) + (b[i] - b[j]) * (b[i] - b[j]));}}
这样写就可以保证每一个元素都是不重复的。
那么这个如何判断输出呢?我们只需要将没有安装卫星的地方考虑进去,而安装卫星的地方由于可以无视距离,是所以就可以不用去管,那么我们跳出的条件就算是数量刚好是全部的地方减去可以安装卫星地区的数量就是我们需要的退出条件。
接下来就只需要按照生成树的模板就可以将题目解出来了
#include<iostream>
#include<cmath>
#include<algorithm>
#define N 1009000
using namespace std;int s, p;struct node
{int x, y;double z;
}q[N];int a[N];//记录坐标
int b[N];//记录坐标int cnt = 0;//记录长度的组数
int cot;//记录有多少个整体
int fa[N];//定义一个并查集数组int cha(int x)
{return fa[x] == x ? x : fa[x] = cha(fa[x]);
}void Union(int x, int y)
{x = cha(x);y = cha(y);if (x == y) return;if(x!=y){fa[x] = y;
// cot--;}
}bool cmp(node x, node y)
{return x.z < y.z;
}
int main()
{cin >> s >> p;// cot = p;for (int i = 1; i <= p; i++){cin >> a[i] >> b[i];}for (int i = 1; i <= p; i++){for (int j = i + 1; j <= p; j++){cnt++;q[cnt].x = i;//这一步和下一行都是为了存编号q[cnt].y = j;q[cnt].z = sqrt((a[i] - a[j]) * (a[i] - a[j]) + (b[i] - b[j]) * (b[i] - b[j]));}}for (int i = 1; i <= N - 10; i++){fa[i] = i;}sort(q + 1, q + 1 + cnt, cmp);double ans=1;int k=0;for (int i = 1; i <= cnt; i++){if(cha(q[i].x)!=cha(q[i].y)){Union(q[i].x,q[i].y);ans=q[i].z;k++;if(k>=p-s){printf("%.2lf\n",ans);return 0;}}}return 0;
}
相关文章:
生成树(习题)
模板】最小生成树 生成树有两种方法,但是我只会克鲁斯卡尔算法,所以接下来下面的的题目都是按照这个算法来实现的,首先来见一下生么是这个算法,在之前的我写的一篇博客中有题使叫修复公路,其实这一题就是使用了这个算…...
ARMv8-AArch64 的异常处理模型详解之异常处理概述Handling exceptions
异常处理模型详解之异常处理概述 一,异常处理相关概念二,异常处理概述 一,异常处理相关概念 在介绍异常处理之前,有必要了解一些关于异常处理状态的术语: 当处理器响应一个异常时,我们称该异常被获取了&a…...
Ubuntu 18.04上安装cuDNN 8.9.6.50:一站式指南
Content 一、前言二、准备工作三、安装步骤1. 启用本地仓库2. 导入CUDA GPG密钥3. 更新仓库元数据4. 安装运行时库5. 安装开发者库6. 安装代码示例7. 另外一种安装办法 四、验证安装1. 验证cuDNN版本2. 测试示例代码 五、总结 一、前言 在深度学习领域,高效的计算资…...
Microsoft Word 超链接
Microsoft Word 超链接 1. 取消超链接2. 自动超链接2.1. 选项2.2. 校对 -> 自动更正选项2.3. Internet 及网络路径替换为超链接 References 1. 取消超链接 Ctrl A -> Ctrl Shift F9 2. 自动超链接 2.1. 选项 2.2. 校对 -> 自动更正选项 2.3. Internet…...
SparkJDBC读写数据库实战
默认的操作 代码val df = spark.read.format("jdbc").option("url", "jdbc:postgresql://localhost:5432/testdb").option("user", "username").option("password", "password").option("driver&q…...
代码随想录 -- 数组
文章目录 二分查找题目描述题解 移除元素题目描述题解:暴力解法题解:双指针法 有序数组的平方题目描述题解:暴力解法题解:双指针法 长度最小的子数组题目描述题解:暴力解法题解:滑动窗口(双指针…...
【国产MCU】-CH32V307-基本定时器(BCTM)
基本定时器(BCTM) 文章目录 基本定时器(BCTM)1、基本定时器(BCTM)介绍2、基本定时器驱动API介绍3、基本定时器使用实例CH32V307的基本定时器模块包含一个16 位可自动重装的定时器(TIM6和TIM7),用于计数和在更新新事件产生中断或DMA 请求。 本文将详细介绍如何使用CH32…...
Node.js开发-fs模块
这里写目录标题 fs模块1) 文件写入2) 文件写入3) 文件移动与重命名4) 文件删除5) 文件夹操作6) 查看资源状态7) 相对路径问题8) __dirname fs模块 fs模块可以实现与硬盘的交互,例如文件的创建、删除、重命名、移动等,还有文件内容的写入、读取ÿ…...
探索Nginx:强大的开源Web服务器与反向代理
一、引言 随着互联网的飞速发展,Web服务器在现代技术架构中扮演着至关重要的角色。Nginx(发音为“engine x”)是一个高性能的HTTP和反向代理服务器,也是一个IMAP/POP3/SMTP代理服务器。Nginx因其卓越的性能、稳定性和灵活性&…...
相机图像质量研究(4)常见问题总结:光学结构对成像的影响--焦距
系列文章目录 相机图像质量研究(1)Camera成像流程介绍 相机图像质量研究(2)ISP专用平台调优介绍 相机图像质量研究(3)图像质量测试介绍 相机图像质量研究(4)常见问题总结:光学结构对成像的影响--焦距 相机图像质量研究(5)常见问题总结:光学结构对成…...
【从Python基础到深度学习】1. Python PyCharm安装及激活
前言: 为了帮助大家快速入门机器学习-深度学习,从今天起我将用100天的时间将大学本科期间的所学所想分享给大家,和大家共同进步。【从Python基础到深度学习】系列博客中我将从python基础开始通过知识和代码实践结合的方式进行知识的分享和记…...
片上网络NoC(3)——拓扑指标
目录 一、概述 二、指标 2.1 与网络流量无关的指标 2.1.1 度(degree) 2.1.2 对分带宽(bisection bandwidth) 2.1.3 网络直径(diameter) 2.2 与网络流量相关的指标 2.2.1 跳数(hop coun…...
二叉树 ---- 所有结点数
普通二叉树的结点数: 递归法: 对二叉树进行前序or后序遍历: typedef struct Tree {int data;Tree* leftChild;Tree* rightChild; }tree,*linklist; //计算普通二叉树的结点数 int nodenums(linklist node) {if(node nullptr) return 0; …...
步步深入 k8s 使用 pv pvc sc 在 nfs 基础上共享存储
博客原文 文章目录 前言集群环境nfs 环境搭建pod 挂载 nfs架构图 pvc 方式挂载 nfs架构图 storageclass 方式动态申请 pv架构图 参考 前言 持久化卷(Persistent Volume, PV)允许用户将外部存储映射到集群,而持久化卷申请(Persist…...
Stable Diffusion 模型下载:Disney Pixar Cartoon Type A(迪士尼皮克斯动画片A类)
本文收录于《AI绘画从入门到精通》专栏,专栏总目录:点这里。 文章目录 模型介绍生成案例案例一案例二案例三案例四案例五案例六案例七案例八案例九案例十...
Modelsim10.4安装
简介(了解,可跳过) modelsim是Mentor公司开发的优秀的HDL语言仿真软件。 它能提供友好的仿真环境,采用单内核支持VHDL和Verilog混合仿真的仿真器。它采用直接优化的编译技术、Tcl/Tk技术和单一内核仿真技术,编译仿真速…...
Java基于微信小程序的医院核酸检测服务系统,附源码
博主介绍:✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 🍅文末获取源码联系🍅 👇🏻 精彩专栏推荐订阅👇…...
VC++ 绘制折线学习
win32 有三个绘制折线的函数; Polyline,根据给定点数组绘制折线; PolylineTo,除了绘制也更新当前位置; PolyPolyline,绘制多条折线,第一个参数是点数组,第二个参数是一个数组、指…...
速盾:dns解析和cdn加速的区别与联系
DNS解析和CDN加速是两种不同的网络技术,但在网站访问过程中起到了相互协作的作用。 首先,DNS解析(Domain Name System)是将域名转换为IP地址的过程。当用户输入一个网址时,计算机会先向本地DNS服务器发送一个查询请求…...
C++ Qt框架开发 | 基于Qt框架开发实时成绩显示排序系统(3) 保存表格数据
对上两篇篇的工作C Qt框架开发| 基于Qt框架开发实时成绩显示排序系统(1)-CSDN博客和C Qt框架开发 | 基于Qt框架开发实时成绩显示排序系统(2)折线图显示-CSDN博客继续优化,增加一个保存按钮,用于保存成绩数据…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
【Go语言基础【13】】函数、闭包、方法
文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数(函数作为参数、返回值) 三、匿名函数与闭包1. 匿名函数(Lambda函…...
C++实现分布式网络通信框架RPC(2)——rpc发布端
有了上篇文章的项目的基本知识的了解,现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...
es6+和css3新增的特性有哪些
一:ECMAScript 新特性(ES6) ES6 (2015) - 革命性更新 1,记住的方法,从一个方法里面用到了哪些技术 1,let /const块级作用域声明2,**默认参数**:函数参数可以设置默认值。3&#x…...
【Linux】Linux安装并配置RabbitMQ
目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的,需要先安…...
Mysql故障排插与环境优化
前置知识点 最上层是一些客户端和连接服务,包含本 sock 通信和大多数jiyukehuduan/服务端工具实现的TCP/IP通信。主要完成一些简介处理、授权认证、及相关的安全方案等。在该层上引入了线程池的概念,为通过安全认证接入的客户端提供线程。同样在该层上可…...
java 局域网 rtsp 取流 WebSocket 推送到前端显示 低延迟
众所周知 摄像头取流推流显示前端延迟大 传统方法是服务器取摄像头的rtsp流 然后客户端连服务器 中转多了,延迟一定不小。 假设相机没有专网 公网 1相机自带推流 直接推送到云服务器 然后客户端拉去 2相机只有rtsp ,边缘服务器拉流推送到云服务器 …...
