生成树(习题)
模板】最小生成树
生成树有两种方法,但是我只会克鲁斯卡尔算法,所以接下来下面的的题目都是按照这个算法来实现的,首先来见一下生么是这个算法,在之前的我写的一篇博客中有题使叫修复公路,其实这一题就是使用了这个算法:用一个结构体记录两个区域的编号,和着两条区域之间道路的价值,再利用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博客继续优化,增加一个保存按钮,用于保存成绩数据…...
使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...
【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
