【图论经典题目讲解】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 个点的有向图,初始没有边,接下来有 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 1∼4 的线段树,形式如下:
如果当前为 2 2 2 操作,且为 1 ∼ 3 1\sim 3 1∼3 每个点连向 4 4 4,权值为 10 10 10,操作如下所示:
即,将区间 1 ∼ 2 1\sim 2 1∼2 和 3 ∼ 3 3\sim 3 3∼3 连向 4 4 4 即可,不过此时发现,图中为有向图,而现在是无向图所以我们要对于图中的每一条边标记方向和权值(这里线段树就是一张图,叶子节点就是我们的 1 ∼ n 1\sim n 1∼n 节点)
其中,为何线段树上的边方向都为向父亲节点?那是因为 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 个点的有向图,初始没有边,接下来有 q q q 次操作,形式如下: 1 u v w 表示…...
【AIGC】Stable Diffusion的采样器入门
在 Stable Diffusion 中,采样器(Sampler)是指用于生成图像的一种技术或方法,它决定了模型如何从潜在空间中抽样并生成图像。采样器在生成图像的过程中起着重要作用,影响着生成图像的多样性、质量和创造性。以下是对 St…...
【Python】通过conda安装Python的IDE
背景 系统:win11 软件:anaconda Navigator 问题现象:①使用Navigator安装jupyter notebook以及Spyder IDE 一直转圈。②然后进入anaconda prompt执行conda install jupyter notebook一直卡在Solving environment/-\。 类似问题: …...
基于HTML5实现动态烟花秀效果(含音效和文字)实战
目录 前言 一、烟花秀效果功能分解 1、功能分解 2、界面分解 二、HTML功能实现 1、html界面设计 2、背景音乐和燃放触发 3、燃放控制 4、对联展示 5、脚本引用即文本展示 三、脚本调用及实现 1、烟花燃放 2、燃放响应 3、烟花canvas创建 4、燃放声音控制 5、实际…...
「数据结构」栈和队列
栈 栈的基本概念 定义 栈是只允许在一端进行插入或删除操作的线性表栈顶:线性表允许进行插入删除的那一端栈底:固定的,不允许进行插入和删除的另一端空栈:不含任何元素特点:后进先出(LIFO) 基…...
【机器学习笔记】5 机器学习实践
数据集划分 子集划分 训练集(Training Set):帮助我们训练模型,简单的说就是通过训练集的数据让我们确定拟合曲线的参数。 验证集(Validation Set):也叫做开发集( Dev Set …...
C++ //练习 7.5 在你的Person类中提供一些操作使其能够返回姓名和住址。这些函数是否应该是const的呢?解释原因。
C Primer(第5版) 练习 7.5 练习 7.5 在你的Person类中提供一些操作使其能够返回姓名和住址。这些函数是否应该是const的呢?解释原因。 环境:Linux Ubuntu(云服务器) 工具:vim 解释 姓名大概…...
python系统学习Day2
section3 python Foudamentals part one:data types and variables 数据类型:整数、浮点数、字符串、布尔值、空值 #整型,没有大小限制 >>>9 / 3 #3.0 >>>10 // 3 #3 地板除 >>>10 % 3 #1 取余#浮点型ÿ…...
学习笔记——ENM模拟
学习笔记——ENM模拟 文章目录 前言一、文献一1. 材料与方法1.1. 大致概念1.2. 生态模型的构建1.2.1. 数据来源:1.2.2. 数据处理:1.2.3. 模型参数优化: 1.3. 适生情况预测1.3.1. 预测模型构建1.3.2. 适生区划分 1.4. 模型的评估与验证 2. 结果…...
数值类型的运算方式总结
提纲1:常见的位运算使用场景 提纲2:整数类型运算时的类型溢出问题,产生原因以及解决办法 提纲3:浮点类型运算时的精度丢失问题,产生原因以及解决办法 数值类型(6种)分为: 整型&…...
【Redis快速入门】Redis三种集群搭建配置(主从集群、哨兵集群、分片集群)
个人名片: 🐼作者简介:一名大三在校生,喜欢AI编程🎋 🐻❄️个人主页🥇:落798. 🐼个人WeChat:hmmwx53 🕊️系列专栏:🖼️…...
[嵌入式系统-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应用范式
先说观点:关于AI应用,通常都会聊准召。但在安全等模糊标准的场景下,事实上不存在准召的定义。因此,AI的目标应该是尽可能的“像人”。而想要评价有多“像人”,就先需要将人的工作数字化。而AI Agent是能够将数字化、自…...
Stable Diffusion 模型下载:ToonYou(平涂卡通)
本文收录于《AI绘画从入门到精通》专栏,专栏总目录:点这里。 文章目录 模型介绍生成案例案例一案例二案例三案例四案例五案例六案例七案例八案例九案例十...
机器学习:分类决策树(Python)
一、各种熵的计算 entropy_utils.py import numpy as np # 数值计算 import math # 标量数据的计算class EntropyUtils:"""决策树中各种熵的计算,包括信息熵、信息增益、信息增益率、基尼指数。统一要求:按照信息增益最大、信息增益率…...
红队打靶练习: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:1 date: 2024-02-16 14:53:49 updated: 2024-02-16 15:08:49 categories: WriteUp:Cyber-Range excerpt: 主机发现、目标信息扫描、源码 js 文件泄露敏感信息、hydra 爆破邮件服务(pop3)、邮件泄露敏…...
html的表格标签
html的表格标签 table标签:表示整个表格tr:表示表格的一行td:表示一个单元格th:表示表头单元格.会居中加粗thead:表格的头部区域 (注意和th区分,范围是比th要大的).tbody:表格得到主体区域. table包含tr , tr包含td或者th. 表格标签有一些属性,可以用于设置大小边…...
蓝桥杯(Web大学组)2022省赛真题:展开你的扇子
思路: transform-origin: center bottom;使盒子旋转时,以底部的中心为坐标原点(题目已给出) 对每个盒子使用transform: rotate();实现旋转 笔记: 设置悬浮旋转时, #box div:hover #item6{ } 为什…...
复习基础知识1
局部变量 写程序时,程序员经常会用到局部变量 汇编中寄存器、栈,可写区段、堆,函数的局部变量该存在哪里呢? 注意:局部变量有易失性 一旦函数返回,则所有局部变量会失效。 考虑到这种特性,人们…...
3分钟搞定Mac外接显示器控制:MonitorControl完全指南
3分钟搞定Mac外接显示器控制:MonitorControl完全指南 【免费下载链接】MonitorControl MonitorControl/MonitorControl: MonitorControl 是一款开源的Mac应用程序,允许用户直接控制外部显示器的亮度、对比度和其他设置,而无需依赖原厂提供的软…...
深入解析Golang中的占位符:%w、%v、%s的应用与最佳实践
1. Golang占位符基础入门 刚开始接触Golang时,fmt包里的那些百分号开头的占位符确实让我有点懵。记得第一次看到%s、%v、%w这些符号时,我还以为是什么特殊运算符。后来在实际项目中用多了才发现,这些看似简单的占位符,其实是Gola…...
云容笔谈开源镜像优势:免编译、免依赖、BF16原生支持,开箱即生成
云容笔谈开源镜像优势:免编译、免依赖、BF16原生支持,开箱即生成 最近在尝试各种AI图像生成工具时,我发现了一个很有意思的现象:很多工具要么安装配置复杂,要么生成效果不尽如人意,特别是想要生成具有东方…...
光纤布拉格光栅(FBG)笔记【2】:传感机制与布拉格波长调谐分析
1. 光纤布拉格光栅的传感机制揭秘 第一次接触光纤布拉格光栅(FBG)传感时,我完全被它"以光测万物"的能力震撼了。这根比头发还细的光纤,竟然能精准感知温度、应变等物理量的变化。经过多次实验验证,我发现它的核心秘密就藏在布拉格波…...
9大核心优势!Outfit字体全方位应用指南:从安装到精通
9大核心优势!Outfit字体全方位应用指南:从安装到精通 【免费下载链接】Outfit-Fonts The most on-brand typeface 项目地址: https://gitcode.com/gh_mirrors/ou/Outfit-Fonts Outfit字体作为一款专业开源无衬线字体,凭借9种完整字重体…...
Phi-4-Reasoning-Vision应用场景:法律文书配图证据链推理系统
Phi-4-Reasoning-Vision应用场景:法律文书配图证据链推理系统 1. 法律文书配图证据链推理系统概述 在法律实务中,证据链的构建往往需要处理大量图文混合材料。传统人工分析方式存在效率低下、主观性强、容易遗漏细节等问题。基于Phi-4-Reasoning-Visio…...
OpenClaw任务编排:GLM-4.7-Flash多步骤自动化设计
OpenClaw任务编排:GLM-4.7-Flash多步骤自动化设计 1. 为什么需要任务编排 上周我需要整理一批技术文档,这个任务包含多个步骤:从不同文件夹收集Markdown文件、统一格式、生成摘要、最后打包发送给团队成员。手动操作不仅耗时,还…...
科研加速器:GLM-4.7-Flash驱动OpenClaw自动整理文献综述
科研加速器:GLM-4.7-Flash驱动OpenClaw自动整理文献综述 1. 为什么需要自动化文献整理 作为每天需要阅读十几篇论文的科研工作者,我发现自己至少有30%的时间花在了机械性劳动上——下载PDF、重命名文件、提取关键结论、整理参考文献格式。这些工作虽然…...
从零到上线:用Vue3+AntV G2快速搭建企业级数据大屏
从零到上线:用Vue3AntV G2快速搭建企业级数据大屏 在数字化转型浪潮中,数据可视化已成为企业决策的重要支撑。想象这样一个场景:会议室里,高管们围坐在大屏前,实时业务数据通过动态图表清晰呈现,关键指标一…...
VSCode配置STM32标准库开发环境:手把手解决core_cm3.c编译报错与头文件路径问题
VSCode搭建STM32开发环境:解决标准库兼容性与智能感知难题 当开发者从Keil或IAR转向VSCode时,往往会遇到两个棘手的拦路虎:标准库与GCC的兼容性问题,以及代码智能感知的缺失。本文将深入解决这两个核心痛点,带你构建一…...
