当前位置: 首页 > news >正文

生成树(习题)

模板】最小生成树

生成树有两种方法,但是我只会克鲁斯卡尔算法,所以接下来下面的的题目都是按照这个算法来实现的,首先来见一下生么是这个算法,在之前的我写的一篇博客中有题使叫修复公路,其实这一题就是使用了这个算法:用一个结构体记录两个区域的编号,和着两条区域之间道路的价值,再利用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;
}

相关文章:

生成树(习题)

模板】最小生成树 生成树有两种方法&#xff0c;但是我只会克鲁斯卡尔算法&#xff0c;所以接下来下面的的题目都是按照这个算法来实现的&#xff0c;首先来见一下生么是这个算法&#xff0c;在之前的我写的一篇博客中有题使叫修复公路&#xff0c;其实这一题就是使用了这个算…...

ARMv8-AArch64 的异常处理模型详解之异常处理概述Handling exceptions

异常处理模型详解之异常处理概述 一&#xff0c;异常处理相关概念二&#xff0c;异常处理概述 一&#xff0c;异常处理相关概念 在介绍异常处理之前&#xff0c;有必要了解一些关于异常处理状态的术语&#xff1a; 当处理器响应一个异常时&#xff0c;我们称该异常被获取了&a…...

Ubuntu 18.04上安装cuDNN 8.9.6.50:一站式指南

Content 一、前言二、准备工作三、安装步骤1. 启用本地仓库2. 导入CUDA GPG密钥3. 更新仓库元数据4. 安装运行时库5. 安装开发者库6. 安装代码示例7. 另外一种安装办法 四、验证安装1. 验证cuDNN版本2. 测试示例代码 五、总结 一、前言 在深度学习领域&#xff0c;高效的计算资…...

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…...

代码随想录 -- 数组

文章目录 二分查找题目描述题解 移除元素题目描述题解&#xff1a;暴力解法题解&#xff1a;双指针法 有序数组的平方题目描述题解&#xff1a;暴力解法题解&#xff1a;双指针法 长度最小的子数组题目描述题解&#xff1a;暴力解法题解&#xff1a;滑动窗口&#xff08;双指针…...

【国产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模块可以实现与硬盘的交互&#xff0c;例如文件的创建、删除、重命名、移动等&#xff0c;还有文件内容的写入、读取&#xff…...

探索Nginx:强大的开源Web服务器与反向代理

一、引言 随着互联网的飞速发展&#xff0c;Web服务器在现代技术架构中扮演着至关重要的角色。Nginx&#xff08;发音为“engine x”&#xff09;是一个高性能的HTTP和反向代理服务器&#xff0c;也是一个IMAP/POP3/SMTP代理服务器。Nginx因其卓越的性能、稳定性和灵活性&…...

相机图像质量研究(4)常见问题总结:光学结构对成像的影响--焦距

系列文章目录 相机图像质量研究(1)Camera成像流程介绍 相机图像质量研究(2)ISP专用平台调优介绍 相机图像质量研究(3)图像质量测试介绍 相机图像质量研究(4)常见问题总结&#xff1a;光学结构对成像的影响--焦距 相机图像质量研究(5)常见问题总结&#xff1a;光学结构对成…...

【从Python基础到深度学习】1. Python PyCharm安装及激活

前言&#xff1a; 为了帮助大家快速入门机器学习-深度学习&#xff0c;从今天起我将用100天的时间将大学本科期间的所学所想分享给大家&#xff0c;和大家共同进步。【从Python基础到深度学习】系列博客中我将从python基础开始通过知识和代码实践结合的方式进行知识的分享和记…...

片上网络NoC(3)——拓扑指标

目录 一、概述 二、指标 2.1 与网络流量无关的指标 2.1.1 度&#xff08;degree&#xff09; 2.1.2 对分带宽&#xff08;bisection bandwidth&#xff09; 2.1.3 网络直径&#xff08;diameter&#xff09; 2.2 与网络流量相关的指标 2.2.1 跳数&#xff08;hop coun…...

二叉树 ---- 所有结点数

普通二叉树的结点数&#xff1a; 递归法&#xff1a; 对二叉树进行前序or后序遍历&#xff1a; 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架构图 参考 前言 持久化卷&#xff08;Persistent Volume, PV&#xff09;允许用户将外部存储映射到集群&#xff0c;而持久化卷申请&#xff08;Persist…...

Stable Diffusion 模型下载:Disney Pixar Cartoon Type A(迪士尼皮克斯动画片A类)

本文收录于《AI绘画从入门到精通》专栏,专栏总目录:点这里。 文章目录 模型介绍生成案例案例一案例二案例三案例四案例五案例六案例七案例八案例九案例十...

Modelsim10.4安装

简介&#xff08;了解&#xff0c;可跳过&#xff09; modelsim是Mentor公司开发的优秀的HDL语言仿真软件。 它能提供友好的仿真环境&#xff0c;采用单内核支持VHDL和Verilog混合仿真的仿真器。它采用直接优化的编译技术、Tcl/Tk技术和单一内核仿真技术&#xff0c;编译仿真速…...

Java基于微信小程序的医院核酸检测服务系统,附源码

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…...

VC++ 绘制折线学习

win32 有三个绘制折线的函数&#xff1b; Polyline&#xff0c;根据给定点数组绘制折线&#xff1b; PolylineTo&#xff0c;除了绘制也更新当前位置&#xff1b; PolyPolyline&#xff0c;绘制多条折线&#xff0c;第一个参数是点数组&#xff0c;第二个参数是一个数组、指…...

速盾:dns解析和cdn加速的区别与联系

DNS解析和CDN加速是两种不同的网络技术&#xff0c;但在网站访问过程中起到了相互协作的作用。 首先&#xff0c;DNS解析&#xff08;Domain Name System&#xff09;是将域名转换为IP地址的过程。当用户输入一个网址时&#xff0c;计算机会先向本地DNS服务器发送一个查询请求…...

C++ Qt框架开发 | 基于Qt框架开发实时成绩显示排序系统(3) 保存表格数据

对上两篇篇的工作C Qt框架开发| 基于Qt框架开发实时成绩显示排序系统&#xff08;1&#xff09;-CSDN博客和C Qt框架开发 | 基于Qt框架开发实时成绩显示排序系统&#xff08;2&#xff09;折线图显示-CSDN博客继续优化&#xff0c;增加一个保存按钮&#xff0c;用于保存成绩数据…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...

Git常用命令完全指南:从入门到精通

Git常用命令完全指南&#xff1a;从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...