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

【图论经典题目讲解】CF786B - Legacy 一道线段树优化建图的经典题目

C F 786 B − L e g a c y \mathrm{CF786B - Legacy} CF786BLegacy

D e s c r i p t i o n \mathrm{Description} Description

给定 1 1 1 n n n 个点的有向图,初始没有边,接下来有 q q q 次操作,形式如下:

  • 1 u v w 表示从 u u u v v v 连接 1 1 1 条长度为 w w w 的有向边
  • 2 u l r w 表示从 u u u i i i i ∈ [ l , r ] i\in [l,r] i[l,r])连接 1 1 1 条长度为 w w w 的有向边
  • 3 u l r w 表示从 i i i i ∈ [ l , r ] i\in [l,r] i[l,r])向 u u u 连接 1 1 1 条长度为 w w w 的有向边

输出从 S S S 点到 i i i 点( i ∈ [ 1 , n ] i\in [1,n] i[1,n])的最短路长度。

S o l u t i o n \mathrm{Solution} Solution

观察可知,最多会建立 1 0 5 × 1 0 5 = 1 0 10 10^5\times 10^5 = 10^{10} 105×105=1010 条边,故必定超时。

此时,需要使用 线段树优化建图,这里展开简单说一下:

对于 1 1 1 棵存储点为 1 ∼ 4 1\sim 4 14 的线段树,形式如下:

image-20240215212043652

如果当前为 2 2 2 操作,且为 1 ∼ 3 1\sim 3 13 每个点连向 4 4 4,权值为 10 10 10,操作如下所示:

image-20240215212212466

即,将区间 1 ∼ 2 1\sim 2 12 3 ∼ 3 3\sim 3 33 连向 4 4 4 即可,不过此时发现,图中为有向图,而现在是无向图所以我们要对于图中的每一条边标记方向和权值(这里线段树就是一张图,叶子节点就是我们的 1 ∼ n 1\sim n 1n 节点)

image-20240215212641895

其中,为何线段树上的边方向都为向父亲节点?那是因为 1 1 1 2 2 2 号点只有这样才能顺着边走到 4 4 4 号节点,对于为何权值设为 0 0 0,因为这是 1 1 1 条虚边(不存在的),不能对最短路做出任何贡献。

不过,上文是区间连节点,当是节点连区间的时候(操作 3 3 3)边都是正好反着的,所以再建 1 1 1 棵线段树即可(不过没必要真的去再建 1 1 1 棵,具体见代码)

C o d e Code Code

#include <bits/stdc++.h>
#define int long longusing namespace std;typedef pair<int, int> PII;
typedef long long LL;const int SIZE = 4e6 + 10, SIZE2 = 1e6 + 10;int N, Q, S;
int h[SIZE2], e[SIZE], ne[SIZE], w[SIZE], idx;
int Id[2], Dist[SIZE2], Vis[SIZE2];
struct Segment
{int l, r;int L, R;
}Tree[SIZE2 << 2];void add(int a, int b, int c)
{e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}int Build(int l, int r, int Sd, int k)
{if (l == r){Tree[l] = {l, l};return l;}int P = ++ Id[k];Tree[P] = {l, r};int mid = l + r >> 1;Tree[P].L = Build(l, mid, Sd, k), Tree[P].R = Build(mid + 1, r, Sd, k);if (!Sd) add(Tree[P].L, P, 0), add(Tree[P].R, P, 0);else add(P, Tree[P].L, 0), add(P, Tree[P].R, 0);return P;
}void Add(int u, int l, int r, int p, int w, int Sd)
{if (Tree[u].l >= l && Tree[u].r <= r){if (!Sd) add(u, p, w);else add(p, u, w);return;}int mid = Tree[u].l + Tree[u].r >> 1;if (mid >= l) Add(Tree[u].L, l, r, p, w, Sd);if (mid < r) Add(Tree[u].R, l, r, p, w, Sd);
}void Dijkstra(int S)
{memset(Dist, 0x3f, sizeof Dist);memset(Vis, 0, sizeof Vis);priority_queue<PII, vector<PII>, greater<PII>> Heap;Heap.push({0, S}), Dist[S] = 0;while (Heap.size()){auto Tmp = Heap.top();Heap.pop();int u = Tmp.second;if (Vis[u]) continue;Vis[u] = 1;for (int i = h[u]; ~i; i = ne[i]){int j = e[i];if (Dist[j] > Dist[u] + w[i]){Dist[j] = Dist[u] + w[i];Heap.push({Dist[j], j});}}}
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);memset(h, -1, sizeof h);cin >> N >> Q >> S;if (N == 1){cout << 0 << endl;return 0;}Id[0] = N;Build(1, N, 0, 0);Id[1] = Id[0];Build(1, N, 1, 1);while (Q --){int Op, v, u, l, r, w;cin >> Op >> u;if (Op == 1){cin >> v >> w;add(u, v, w);}else if (Op == 2){cin >> l >> r >> w;Add(Id[0] + 1, l, r, u, w, 1);}else{cin >> l >> r >> w;Add(N + 1, l, r, u, w, 0);}}Dijkstra(S);for (int i = 1; i <= N; i ++)if (Dist[i] >= 1e18) cout << -1 << " ";else cout << Dist[i] << " ";return 0;
}

相关文章:

【图论经典题目讲解】CF786B - Legacy 一道线段树优化建图的经典题目

C F 786 B − L e g a c y \mathrm{CF786B - Legacy} CF786B−Legacy D e s c r i p t i o n \mathrm{Description} Description 给定 1 1 1 张 n n n 个点的有向图&#xff0c;初始没有边&#xff0c;接下来有 q q q 次操作&#xff0c;形式如下&#xff1a; 1 u v w 表示…...

【AIGC】Stable Diffusion的采样器入门

在 Stable Diffusion 中&#xff0c;采样器&#xff08;Sampler&#xff09;是指用于生成图像的一种技术或方法&#xff0c;它决定了模型如何从潜在空间中抽样并生成图像。采样器在生成图像的过程中起着重要作用&#xff0c;影响着生成图像的多样性、质量和创造性。以下是对 St…...

【Python】通过conda安装Python的IDE

背景 系统&#xff1a;win11 软件&#xff1a;anaconda Navigator 问题现象&#xff1a;①使用Navigator安装jupyter notebook以及Spyder IDE 一直转圈。②然后进入anaconda prompt执行conda install jupyter notebook一直卡在Solving environment/-\。 类似问题&#xff1a; …...

基于HTML5实现动态烟花秀效果(含音效和文字)实战

目录 前言 一、烟花秀效果功能分解 1、功能分解 2、界面分解 二、HTML功能实现 1、html界面设计 2、背景音乐和燃放触发 3、燃放控制 4、对联展示 5、脚本引用即文本展示 三、脚本调用及实现 1、烟花燃放 2、燃放响应 3、烟花canvas创建 4、燃放声音控制 5、实际…...

「数据结构」栈和队列

栈 栈的基本概念 定义 栈是只允许在一端进行插入或删除操作的线性表栈顶&#xff1a;线性表允许进行插入删除的那一端栈底&#xff1a;固定的&#xff0c;不允许进行插入和删除的另一端空栈&#xff1a;不含任何元素特点&#xff1a;后进先出&#xff08;LIFO&#xff09; 基…...

【机器学习笔记】5 机器学习实践

数据集划分 子集划分 训练集&#xff08;Training Set&#xff09;&#xff1a;帮助我们训练模型&#xff0c;简单的说就是通过训练集的数据让我们确定拟合曲线的参数。 验证集&#xff08;Validation Set&#xff09;&#xff1a;也叫做开发集&#xff08; Dev Set &#xf…...

C++ //练习 7.5 在你的Person类中提供一些操作使其能够返回姓名和住址。这些函数是否应该是const的呢?解释原因。

C Primer&#xff08;第5版&#xff09; 练习 7.5 练习 7.5 在你的Person类中提供一些操作使其能够返回姓名和住址。这些函数是否应该是const的呢&#xff1f;解释原因。 环境&#xff1a;Linux Ubuntu&#xff08;云服务器&#xff09; 工具&#xff1a;vim 解释 姓名大概…...

python系统学习Day2

section3 python Foudamentals part one&#xff1a;data types and variables 数据类型&#xff1a;整数、浮点数、字符串、布尔值、空值 #整型&#xff0c;没有大小限制 >>>9 / 3 #3.0 >>>10 // 3 #3 地板除 >>>10 % 3 #1 取余#浮点型&#xff…...

学习笔记——ENM模拟

学习笔记——ENM模拟 文章目录 前言一、文献一1. 材料与方法1.1. 大致概念1.2. 生态模型的构建1.2.1. 数据来源&#xff1a;1.2.2. 数据处理&#xff1a;1.2.3. 模型参数优化&#xff1a; 1.3. 适生情况预测1.3.1. 预测模型构建1.3.2. 适生区划分 1.4. 模型的评估与验证 2. 结果…...

数值类型的运算方式总结

提纲1&#xff1a;常见的位运算使用场景 提纲2&#xff1a;整数类型运算时的类型溢出问题&#xff0c;产生原因以及解决办法 提纲3&#xff1a;浮点类型运算时的精度丢失问题&#xff0c;产生原因以及解决办法 数值类型&#xff08;6种&#xff09;分为&#xff1a; 整型&…...

【Redis快速入门】Redis三种集群搭建配置(主从集群、哨兵集群、分片集群)

个人名片&#xff1a; &#x1f43c;作者简介&#xff1a;一名大三在校生&#xff0c;喜欢AI编程&#x1f38b; &#x1f43b;‍❄️个人主页&#x1f947;&#xff1a;落798. &#x1f43c;个人WeChat&#xff1a;hmmwx53 &#x1f54a;️系列专栏&#xff1a;&#x1f5bc;️…...

[嵌入式系统-14]:常见实时嵌入式操作系统比较:RT-Thread、uC/OS-II和FreeRTOS、Linux

目录 一、实时嵌入式操作系统 1.1 概述 1.2 什么“实时” 1.3 什么是硬实时和软实时 1.4 什么是嵌入式 1.5 什么操作系统 二、常见重量级操作系统 三、常见轻量级嵌入式操作系统 3.1 概述 3.2 FreeRTOS 3.3 uC/OS-II 3.4 RT-Thread 3.5 RT-Thread、uC/OS-II、Free…...

基于AI Agent探讨:安全领域下的AI应用范式

先说观点&#xff1a;关于AI应用&#xff0c;通常都会聊准召。但在安全等模糊标准的场景下&#xff0c;事实上不存在准召的定义。因此&#xff0c;AI的目标应该是尽可能的“像人”。而想要评价有多“像人”&#xff0c;就先需要将人的工作数字化。而AI Agent是能够将数字化、自…...

Stable Diffusion 模型下载:ToonYou(平涂卡通)

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

机器学习:分类决策树(Python)

一、各种熵的计算 entropy_utils.py import numpy as np # 数值计算 import math # 标量数据的计算class EntropyUtils:"""决策树中各种熵的计算&#xff0c;包括信息熵、信息增益、信息增益率、基尼指数。统一要求&#xff1a;按照信息增益最大、信息增益率…...

红队打靶练习:HACK ME PLEASE: 1

信息收集 1、arp ┌──(root㉿ru)-[~/kali] └─# arp-scan -l Interface: eth0, type: EN10MB, MAC: 00:0c:29:69:c7:bf, IPv4: 192.168.61.128 Starting arp-scan 1.10.0 with 256 hosts (https://github.com/royhills/arp-scan) 192.168.61.2 00:50:56:f0:df:20 …...

《VulnHub》GoldenEye:1

title: 《VulnHub》GoldenEye&#xff1a;1 date: 2024-02-16 14:53:49 updated: 2024-02-16 15:08:49 categories: WriteUp&#xff1a;Cyber-Range excerpt: 主机发现、目标信息扫描、源码 js 文件泄露敏感信息、hydra 爆破邮件服务&#xff08;pop3&#xff09;、邮件泄露敏…...

html的表格标签

html的表格标签 table标签:表示整个表格tr:表示表格的一行td:表示一个单元格th:表示表头单元格.会居中加粗thead:表格的头部区域 (注意和th区分,范围是比th要大的).tbody:表格得到主体区域. table包含tr , tr包含td或者th. 表格标签有一些属性&#xff0c;可以用于设置大小边…...

蓝桥杯(Web大学组)2022省赛真题:展开你的扇子

思路&#xff1a; transform-origin: center bottom;使盒子旋转时&#xff0c;以底部的中心为坐标原点&#xff08;题目已给出&#xff09; 对每个盒子使用transform: rotate();实现旋转 笔记&#xff1a; 设置悬浮旋转时&#xff0c; #box div:hover #item6{ } 为什…...

复习基础知识1

局部变量 写程序时&#xff0c;程序员经常会用到局部变量 汇编中寄存器、栈&#xff0c;可写区段、堆&#xff0c;函数的局部变量该存在哪里呢&#xff1f; 注意&#xff1a;局部变量有易失性 一旦函数返回&#xff0c;则所有局部变量会失效。 考虑到这种特性&#xff0c;人们…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...

解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist

现象&#xff1a; android studio报错&#xff1a; [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决&#xff1a; 不要动CMakeLists.…...

华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)

题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...

消防一体化安全管控平台:构建消防“一张图”和APP统一管理

在城市的某个角落&#xff0c;一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延&#xff0c;滚滚浓烟弥漫开来&#xff0c;周围群众的生命财产安全受到严重威胁。就在这千钧一发之际&#xff0c;消防救援队伍迅速行动&#xff0c;而豪越科技消防一体化安全管控平台构建的消防“…...

2.3 物理层设备

在这个视频中&#xff0c;我们要学习工作在物理层的两种网络设备&#xff0c;分别是中继器和集线器。首先来看中继器。在计算机网络中两个节点之间&#xff0c;需要通过物理传输媒体或者说物理传输介质进行连接。像同轴电缆、双绞线就是典型的传输介质&#xff0c;假设A节点要给…...