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

推导部分和——带权并查集

在这里插入图片描述

题解:

带权并查集

引言: 带权并查集是一种进阶的并查集,通常,结点i的权值等于结点i到根节点的距离,对于带权并查集,有两种操作需要掌握——Merge与Find,涉及到路径压缩与维护权值等技巧。

带权并查集的数据结构

  • 使用顺序存储结构,定义结构体数组,其中a[i]的root代表节点 i 的根节点编号,weight代表它与root号节点之间的距离,也就是权值。

    struct node {int root;ll weight;node() :root(0), weight(0) {}
    }a[100005];
    

Find函数+权值合并

  • 首先,在执行整个并查集算法之前,需要首先初始化每一个结点的根节点编号为它本身,意思就是说,每一个结点在初始状态时都被视为一颗单独的并查集树,即:

    for (int i = 1; i <= n; i++) {a[i].root = i;
    }
    
  • 当我们想要去查询一个节点的根节点时,调用find函数:

    • 传入:想要查询的结点编号x

    • 返回: 第x号结点的根节点编号

      //路径压缩+权值合并
      int find(int x) {if (x != a[x].root) {//更新x的根节点int tmp = a[x].root;a[x].root = find(a[x].root);a[x].weight += a[tmp].weight;}return a[x].root;
      }
      
    • 在函数体内:

      • 当结点x的root值为它自己时,即 x == a[x].root 时,直接返回a[x].root
      • 否则,递归查找它根节点的根节点
      • 在递归之前,使用tmp暂存x当前的根节点编号。这是由于在查找的过程中,我们使用了路径压缩的技巧,使a[x].root被赋值为find函数的返回值,但是在后续的计算中,我们又需要使用到这个旧的a[x].root值。
      • 在路径压缩的同时,我们必须要维护权值a[x].weight使其始终等于x号结点到a[x].root号结点的距离
      • 在路径压缩之前,a[x].weight存储的是x到旧的root的距离,但root发生更改后,此时新的权值a[x].weight应该修改为dist(新root,旧root) + dist(旧root,x)才能符合权值的定义,dis(新root, 旧root)将会被递归计算出来,而dis(旧root, x)正是a[x].weight现在存储的值,因此,我们必须要记下旧root的编号才能找到旧root的位置,这也就是tmp发挥的作用。

合并

  • 当我们得到了两个结点之间的距离,并且想要将这两个结点合并,按照并查集的思想,应当先找到他们各自的根节点,然后再将两颗树合并。然而,我们现在所获取的信息并不是根节点的信息,因此我们需要对已知的信息做一个转化:
    • 假设我们现在得到的新的信息是第l-1个节点到第r个节点的距离为w,设第l-1个节点的根节点编号x第r个节点的根节点编号y

    • 首先,我们通过find(l−1)find(l - 1)find(l1)find(r)find(r)find(r)获得x与y的值,经过find函数内部的权值维护之后,此时,a[l-1].weight和a[r].weight已经分别被修改为l-1到x和r到y的距离了,设它们分别为w1和w2.在这里插入图片描述

    • 通过上图,其实我们很容易就能看出x到y的距离为:w+w2−w1w+w_2-w1w+w2w1

    • 在这,我们只需要算出x到y的距离就好了,在后续调用find函数执行路径压缩和权值合并时将会处理掉它,因此,我们合并的操作就是:

      int l, r, w;
      l = read(), r = read(), w = read();
      //x为l-1的根节点,y为r的根节点
      int x = find(l - 1), y = find(r);
      //若l-1与r的根节点不相同
      if (x != y) {//将结点x并入y的子树a[x].root = y;//根据向量的思想计算a[x].weight = w + a[r].weight - a[l - 1].weight;
      }
      

查询

写到这里,这个题目已经接近尾声。(此处再次强调a[i].weight的意义是从第i个节点到第a[i].root个节点的距离,接下来要用的) 当我们维护好了一颗带权并查集树之后,那我们查询区间和就只有两种情况:

  • 设区间左端点为l,右端点为r,则
    • 当l与r的根不相同时,则无法查询出l到r的区间和。
    • 当l与r的根相同时,则有s[l..r]=a[l−1].weight−a[r].weights[l.. r]=a[l-1].weight-a[r].weights[l..r]=a[l1].weighta[r].weight
    • 以图形的方式表达,蓝色部分即为所求的区间和:
      在这里插入图片描述

完整代码:

#include <iostream>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
ll n, m, q;//带权并查集结点
struct node {int root;ll weight;node() :root(0), weight(0) {}
}a[100005];
//快读
int read() {char ch = getchar(); int res = 0;while (ch < '0' || ch>'9') {ch = getchar();}while (!(ch < '0' || ch>'9')) {res = res * 10 + (ch - '0');ch = getchar();}return res;
}
//快写
void print(ll x) {if (x > 9) {print(x / 10);}putchar(x % 10 + '0');
}//路径压缩+权值合并
int find(int x) {if (x != a[x].root) {//更新x的根节点int tmp = a[x].root;a[x].root = find(a[x].root);a[x].weight += a[tmp].weight;}return a[x].root;
}int main()
{cin >> n >> m >> q;for (int i = 1; i <= n; i++) {a[i].root = i;}for (int i = 1; i <= m; i++) {int l, r, w;l = read(), r = read(), w = read();//x为l-1的根节点,y为r的根节点int x = find(l - 1), y = find(r);//若l-1与r的根节点不相同if (x != y) {//将结点x并入y的子树a[x].root = y;//根据向量的思想计算a[x].weight = w + a[r].weight - a[l - 1].weight;}}for (int i = 1; i <= q; i++) {int l, r; cin >> l >> r;if (find(l - 1) != find(r)) {puts("UNKNOWN");}else {print(a[l - 1].weight - a[r].weight);putchar('\n');}}return 0;
}

相关文章:

推导部分和——带权并查集

题解&#xff1a; 带权并查集 引言&#xff1a; 带权并查集是一种进阶的并查集&#xff0c;通常&#xff0c;结点i的权值等于结点i到根节点的距离&#xff0c;对于带权并查集&#xff0c;有两种操作需要掌握——Merge与Find&#xff0c;涉及到路径压缩与维护权值等技巧。 带…...

费解的开关/翻硬币

&#x1f331;博客主页&#xff1a;大寄一场. &#x1f331;系列专栏&#xff1a; 算法 &#x1f618;博客制作不易欢迎各位&#x1f44d;点赞⭐收藏➕关注 题目&#xff1a;费解的开关 你玩过“拉灯”游戏吗&#xff1f; 25盏灯排成一个 55 的方形。 每一个灯都有一个开关&…...

OpenGL中的坐标系

1、2D笛卡尔坐标系2D笛卡尔坐标系跟我们高中的时候学习的坐标系一样&#xff0c;是由x、y决定的。2、3D笛卡尔坐标系3D笛卡尔坐标系坐标由x、y、z决定&#xff0c;满足右手定则。3、视口glViewport(GLint x,GLint y,GLsizei width,GLsizei height)窗口和视口大小可以相同&#…...

Spring——Spring介绍和IOC相关概念

Spring是以Spring Framework为核心&#xff0c;其余的例如Spring MVC&#xff0c; Spring Cloud&#xff0c;Spring Data&#xff0c;Spring Security SpringBoot的基础都是Spring Framework。 Spring Boot可以在简化开发的基础上加速开发。 Spring Cloud分布式开发 Spring有…...

A+B Problem

AB Problem 题目描述 输入两个整数 a,ba, ba,b&#xff0c;输出它们的和&#xff08;∣a∣,∣b∣≤109|a|,|b| \le {10}^9∣a∣,∣b∣≤109&#xff09;。 注意 Pascal 使用 integer 会爆掉哦&#xff01;有负数哦&#xff01;C/C 的 main 函数必须是 int 类型&#xff0c;…...

【ROS学习笔记11】ROS元功能包与launch文件的使用

【ROS学习笔记11】ROS元功能包与launch文件的使用 文章目录【ROS学习笔记11】ROS元功能包与launch文件的使用前言一、ROS元功能包二、ROS节点运行管理launch文件2.1 launch文件标签之launch2.2 launch文件标签之node2.3 launch文件标签之include2.4 launch文件标签之remap2.5 l…...

【python】

print函数 同时输出多行变量 print(a, b, sep\n) (23条消息) python3 中print函数参数详解&#xff0c;print(*values, sep , end\n, filesys.stdout, flushFalse)中参数介绍_sep,_phantom-dapeng的博客-CSDN博客 input() 输入浮点数&#xff0c;不能用int(input()) int()…...

充电协议: 快充协议,如何选充电宝?

快充协议(存在两种&#xff1a;电压; 电流) 目前市面上的快充技术大多遵循2个技术方向&#xff1a; 以高通QC、联发科PEP、华为FCP为首的高压低电流快充技术&#xff1b; 另一种就是以OPPO的VOOC以及华为SCP为首的低电压大电流快充技术。 目前常见的快充标准还有三星AFC、联发…...

视觉SLAM十四讲ch6 非线性优化笔记

视觉SLAM十四讲ch6 非线性优化笔记本讲目标上讲回顾状态估计问题非线性最小二乘Gauss-Newton&#xff1a;高斯牛顿Levenburg-Marquadt&#xff1a;列文伯格-马夸尔特小结实践&#xff1a;CERES实践&#xff1a;G2O本讲目标 理解最小二乘法的含义和处理方式。 理解Gauss-Newton…...

Nikto工具使用指南

NiktoNikto是一款开源网站服务器扫描器&#xff0c;使用Perl开发&#xff0c;可以对服务器进行全面扫描&#xff0c;包括6400多个潜在危险的文件/cgi(通用网关接口&#xff08;Common Gateway Interface&#xff09;),废话不多说&#xff0c;直接上命令&#xff1a;基本测试&am…...

Git(4)之基本工具

Git基础之基本工具 Author&#xff1a;onceday date&#xff1a;2023年3月5日 满满长路有人对你微笑过嘛… windows安装可参考文章&#xff1a;git简易配置_onceday_CSDN博客 參考文档&#xff1a; 《progit2.pdf》&#xff0c;Progit2 Github。《git-book.pdf》 文章目录…...

好书推荐。

个人喜欢看传记&#xff0c;散文&#xff0c;历史等 二战名人传记&#xff0c;苏联列宁&#xff0c;朱可夫&#xff0c;斯大林等 英国首相丘吉尔&#xff0c;美国富兰克林&#xff0c;中国毛泽东等 创业&#xff1a;比尔盖&#xff0c;扎克伯格&#xff0c;苹果公司创始人乔…...

[Pytorch]DataSet和DataLoader逐句详解

将自己的数据集引入Pytorch是搭建属于自己的神经网络的重要一步&#xff0c;这里我设计了一个简单的实验&#xff0c;结合这个实验代码&#xff0c;我将逐句教会大家如何将数据引入DataLoader。 这里以目标检测为例&#xff0c;一个batch中包含图片文件、先验框的框体坐标、目标…...

【Kettle-佛系总结】

Kettle-佛系总结Kettle-佛系总结1.kettle介绍2.kettle安装3.kettle目录介绍4.kettle核心概念1.转换2.步骤3.跳&#xff08;Hop&#xff09;4.元数据5.数据类型6.并行7.作业5.kettle转换1.输入控件1.csv文件输入2.文本文件输入3.Excel输入4.XML输入5.JSON输入6.表输入2.输出控件…...

JavaSE网络编程

JavaSE网络编程一、基本概念二、常用类三、使用方法1、创建服务器端Socket2、创建客户端Socket3、创建URL对象JavaSE中的网络编程模块提供了一套完整的网络编程接口&#xff0c;可以方便地实现各种基于网络的应用程序。本文将介绍JavaSE中网络编程模块的基本知识、常用类以及使…...

9万字“联、管、用”三位一体雪亮工程整体建设方案

本资料来源公开网络&#xff0c;仅供个人学习&#xff0c;请勿商用。部分资料内容&#xff1a; 1、 总体设计方案 围绕《公共安全视频监控建设联网应用”十三五”规划方案》中的总体架构和一总两分结构要求的基础上&#xff0c;项目将以“加强社会公共安全管理&#xff0c;提高…...

springboot自动装配原理

引言 springboot的自动装配是其重要特性之一&#xff0c;在使用中我们只需在maven中引入需要的starter&#xff0c;然后相应的Bean便会自动注册到容器中。例如&#xff1a; <dependency><groupId>org.springframework.boot</groupId><artifactId>spr…...

Docker学习(二十)什么是分层存储?

目录1.简介2.什么是 Union Mount&#xff1f;3.分层介绍1&#xff09;lowerdir 层&#xff08;镜像层&#xff09;2&#xff09;upperdir 层&#xff08;容器层&#xff09;3&#xff09;merged 层4.工作原理1&#xff09;读&#xff1a;2&#xff09;写&#xff1a;3&#xff…...

Vue组件进阶(动态组件,组件缓存,组件插槽,具名插槽,作用域插槽)与自定义指令

Vue组件进阶与自定义指令一、Vue组件进阶1.1 动态组件1.2 组件缓存1.3 组件激活和非激活1.4 组件插槽1.5 具名插槽1.6 作用域插槽1.7 作用域插槽使用场景二、自定义指令2.1 自定义指令--注册2.2 自定义指令-传参一、Vue组件进阶 1.1 动态组件 多个组件使用同一个挂载点&#x…...

僵尸进程与孤儿进程

概念 在 Unix/Linux 系统中&#xff0c;正常情况下&#xff0c;子进程是通过父进程创建的&#xff0c;且两者的运行是相互独立的&#xff0c;父进程永远无法预测子进程到底什么时候结束。当一个进程调用 exit 命令结束自己的生命时&#xff0c;其实它并没有真正的被销毁&#…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业&#xff0c;那宇树科技&#xff08;Unitree&#xff09;必须名列其榜。 最近&#xff0c;宇树科技的一项新变动消息在业界引发了不少关注和讨论&#xff0c;即&#xff1a; 宇树向其合作伙伴发布了一封公司名称变更函称&#xff0c;因…...