Acwing342

这个代码实现了一种结合 连通块分解拓扑排序Dijkstra 算法 的复杂图的最短路径计算方法,适用于含有两类边的图结构:普通边(在连通块内)和特殊边(跨连通块)。

以下是详细的代码讲解,逐步解析每一部分:


代码结构

1. 数据结构定义

const int N = 25010, M = 150010;
int n, mr, mp, S; // 城镇数量、普通边数量、特殊边数量、起点
int h[N], e[M], ne[M], w[M], idx; // 邻接表存储图
int id[N]; // 每个点属于的连通块编号
vector<int> block[N]; // 每个连通块包含的点
int bid; // 连通块编号
int dist[N]; // 到起点的最短距离
int din[N]; // 每个连通块的入度
bool st[N]; // 标记点是否已经确定最短距离
queue<int> q; // 队列用于拓扑排序
解释
  1. 邻接表:使用链式前向星存储普通边和特殊边。
    • h[u]:存储节点 u 的第一条边索引。
    • e[idx], w[idx], ne[idx]:分别表示边的目标节点、权重和下一条边的索引。
  2. 连通块
    • id[u]:标记节点 (u) 属于哪个连通块。
    • block[bid]:存储每个连通块的节点集合。
  3. 其他变量
    • dist[u]:起点到节点 (u) 的最短路径长度。
    • din[id]:每个连通块的入度。
    • st[u]:标记节点是否已确定最短距离。

2. 边的添加

void add(int a, int b, int c) {e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
  • 使用链式前向星添加边:
    • e[idx]:目标节点。
    • w[idx]:边权重。
    • ne[idx]:指向当前节点的下一条边。

3. 连通块分解

void dfs(int u, int bid) {id[u] = bid; // 标记节点 u 属于连通块 bidblock[bid].push_back(u); // 将节点 u 加入连通块for (int i = h[u]; ~i; i = ne[i]) { // 遍历所有普通边int j = e[i];if (!id[j]) dfs(j, bid); // 如果未访问,则递归}
}
  • 核心思想:通过深度优先搜索 (DFS),将图分解成连通块。
  • 连通块标记:每个连通块分配一个唯一编号 bid,节点 u 的连通块编号存储在 id[u] 中。
  • 只处理普通边:连通块内部的边仅由普通边组成。

4. 连通块内部的 Dijkstra

void dijkstra(int bid) {priority_queue<PII, vector<PII>, greater<PII>> heap;// 将连通块中的所有点加入优先队列for (auto ver : block[bid]) heap.push({dist[ver], ver});while (heap.size()) {auto t = heap.top();heap.pop();int ver = t.y, distance = t.x;if (st[ver]) continue; // 如果最短路径已确定,跳过st[ver] = true;for (int i = h[ver]; ~i; i = ne[i]) {int j = e[i];if (dist[j] > dist[ver] + w[i]) {dist[j] = dist[ver] + w[i];if (id[j] == id[ver]) heap.push({dist[j], j}); // 同连通块内继续松弛}// 如果跨连通块,更新入度并加入拓扑排序队列if (id[j] != id[ver] && --din[id[j]] == 0) q.push(id[j]);}}
}
  • 功能:在连通块内部运行 Dijkstra 算法。
  • 松弛规则
    • 如果邻接点属于同一个连通块,则更新距离并入队。
    • 如果跨连通块,则更新目标连通块的入度,入度为 0 时加入拓扑队列。

5. 拓扑排序 + Dijkstra

void topsort() {memset(dist, 0x3f, sizeof dist); // 初始化最短距离为无穷大dist[S] = 0; // 起点距离为 0for (int i = 1; i <= bid; i++) // 入度为 0 的连通块入队if (din[i] == 0) q.push(i);while (q.size()) {auto t = q.front();q.pop();dijkstra(t); // 对当前连通块运行 Dijkstra}
}
  • 功能:通过拓扑排序计算跨连通块的最短路径。
  • 实现
    1. 初始化所有入度为 0 的连通块,将其加入队列。
    2. 按照拓扑顺序依次处理连通块。
    3. 对于每个连通块,调用 dijkstra 计算其内部的最短路径,并更新跨连通块的依赖关系。

6. 主函数

int main() {cin >> n >> mr >> mp >> S;memset(h, -1, sizeof h); // 初始化邻接表// 读取普通边并构建邻接表while (mr--) {int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c), add(b, a, c);}// 连通块分解for (int i = 1; i <= n; i++)if (!id[i]) dfs(i, ++bid);// 读取特殊边并更新入度while (mp--) {int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c);din[id[b]]++;}topsort(); // 拓扑排序 + 最短路径// 输出结果for (int i = 1; i <= n; i++)if (dist[i] > 0x3f3f3f3f / 2) puts("NO PATH");else cout << dist[i] << endl;return 0;
}

代码流程总结

  1. 普通边与特殊边的构建

    • 普通边用于连通块分解。
    • 特殊边用于跨连通块的连接,记录连通块之间的依赖关系。
  2. 连通块分解

    • 使用 DFS 将图分解为多个连通块,每个连通块内部通过普通边连接。
  3. 拓扑排序

    • 根据特殊边建立连通块之间的依赖关系,通过拓扑排序处理连通块。
  4. Dijkstra + 松弛更新

    • 在连通块内部运行 Dijkstra 算法,计算最短路径。
    • 跨连通块时,使用拓扑顺序更新依赖连通块的最短路径。
  5. 输出结果

    • 若某节点不可达,输出 NO PATH
    • 否则,输出从起点到每个节点的最短距离。

时间复杂度

  1. 连通块分解:(O(n + mr))(DFS 遍历所有节点和普通边)。
  2. 拓扑排序:(O(b + mp))(连通块数 (b) 和特殊边数 (mp))。
  3. Dijkstra:(O(\text{总点数} \cdot \log(\text{总点数})))。

整体复杂度:(O(n + m + b \cdot \log n)),适合稀疏图和多连通块场景。


这段代码巧妙结合了 连通块分解拓扑排序 的思想,高效处理了含两类边的复杂最短路径问题。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/18229.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

ETH钱包地址如何获取 如何购买比特币

首先我们要先注册一个交易所 Gate.io&#xff08;推荐&#xff09;: 点我注册 1、注册很简单&#xff0c;通过手机号就可以进行注册了。 2、获取ETH钱包地址 注册好之后&#xff0c;如图所示&#xff0c;点击“统一账户” 3、通过搜索栏搜索ETH&#xff0c;如下图所示 4、点…

[Docker#11] 容器编排 | .yml | up | 实验: 部署WordPress

目录 1. 什么是 Docker Compose 生活案例 2. 为什么要使用 Docker Compose Docker Compose 的安装 Docker Compose 的功能 使用步骤 核心功能 Docker Compose 使用场景 Docker Compose 文件&#xff08;docker-compose.yml&#xff09; 模仿示例 文件基本结构及常见…

OpenCV基础(1)

1.图像读写与窗口显示 1.1.imread读取图像文件 Mat cv::imread(const string &filename,int flags IMREAD_COLOR); filename&#xff1a;要读取的图像文件名flags&#xff1a;读取模式&#xff0c;可以从枚举cv::ImreadModes中取值&#xff0c;默认取值是IMREAD_COLOR&am…

【优选算法篇】分治乾坤,万物归一:在重组中窥见无声的秩序

文章目录 分治专题&#xff08;二&#xff09;&#xff1a;归并排序的核心思想与进阶应用前言、第二章&#xff1a;归并排序的应用与延展2.1 归并排序&#xff08;medium&#xff09;解法&#xff08;归并排序&#xff09;C 代码实现易错点提示时间复杂度和空间复杂度 2.2 数组…

生产环境centos8 Red Hat8部署ansible and 一键部署mysql两主两从ansible脚本预告

一、各节点服务器创建lvm逻辑卷组 1.初始化磁盘为物理卷&#xff08;PV&#xff09; 命令&#xff1a;sudo pvcreate /dev/vdb 2.创建卷组&#xff08;VG&#xff09; 命令&#xff1a;sudo vgcreate db_vg /dev/vdb 3.创建逻辑卷&#xff08;LV&#xff09; 命令&#xff1a;s…

CNN神经网络

CNN 一 基本概述二 基础知识三 经典案例 今天跟大家聊聊人工智能中的神经网络模型相关内容。神经网络内容庞大,篇幅有限本文主要讲述其中的CNN神经网络模型。 一 基本概述 深度学习(Deep Learning)特指基于深层神经网络模型和方法的机器学习。它是在统计机器学习、人工神经网…

【Ubuntu24.04】VirtualBox安装ubuntu-live-server24.04

目录 0 背景1 下载镜像2 安装虚拟机3 安装UbuntuServer24.044 配置基本环境5 总结0 背景 有了远程连接工具之后,似乎作为服务器的Ubuntu24.04桌面版有点备受冷落了,桌面版的Ubuntu24.04的优势是图形化桌面,是作为一个日常工作的系统来用的,就像Windows,如果要作为服务器来…

【策略模式】最佳实践——Spring IoC实现策略模式全流程深度解析

简介 策略模式是一种行为型设计模式&#xff0c;它定义了一系列算法&#xff0c;并将每一个算法封装起来&#xff0c;使它们可以互相替换&#xff0c;并且使算法的变化不会影响使用算法的客户端。策略模式通过将具体的业务逻辑从上下文&#xff08;Context&#xff09;中剥离出…

企业项目级IDEA设置类注释、方法注释模板(仅增加@author和@date)

文章目录 前言一 设置类注释1.1 添加模板1.2 复制配置 二 设置方法注释2.1 添加模版2.2 设置模版2.3 设置参数变量2.4 配置对应快捷键2.5 配置对应作用域2.6 使用方式 说明 前言 公司代码规范中&#xff0c;需要在标准JavaDoc注释的基础上加上作者和日期。网上虽然有很多现成的…

单片机学习笔记 2. LED灯闪烁

目录 0、实现的功能 1、Keil工程 2、代码实现 0、实现的功能 LED灯闪烁 1、Keil工程 闪烁原理&#xff1a;需要进行软件延时达到人眼能分辨出来的效果。常用的延时方法有软件延时和定时器延时。此次先进行软件延时 具体操作步骤和之前的笔记一致。此次主要利用无符号整型的范…

编辑器vim 命令的学习

1.编辑器Vim 1.vim是一个专注的编辑器 2.是一个支持多模式的编辑器 1.1见一见&#xff1a; vim 的本质也是一条命令 退出来&#xff1a;-> Shift:q 先创建一个文件 再打开这个文件 进入后先按 I 然后就可以输入了 输入完后&#xff0c;保存退出 按Esc --> 来到最后一…

调用门提权

在我写的2.保护模式&#xff0b;段探测这篇文章中&#xff0c;我们提到了S位对于段描述符的控制&#xff0c;之前我们已经介绍了代码段和数据段&#xff0c;现在我们来把目光转到系统段 在这么多中结构里面&#xff0c;我们今天要介绍的就是编号为12的&#xff0c;32位调用门 结…

langchain模型及I/O的封装

langchain安装&#xff1a;pip install langchain-openai https://python.langchain.com/v0.2/docs/integrations/platforms/openai/ 注意&#xff1a;安装后&#xff0c;我们需要在环境变量中配置OPENAI_API_KEY&#xff0c;langchain会自动获取 1.模型的封装 指令生成式模…

阿里斑马智行 2025届秋招 NLP算法工程师

文章目录 个人情况一面/技术面 1h二面/技术面 1h三面/HR面 20min 个人情况 先说一下个人情况&#xff1a; 学校情况&#xff1a;211本中9硕&#xff0c;本硕学校都一般&#xff0c;本硕都是计算机科班&#xff0c;但研究方向并不是NLP&#xff0c;而是图表示学习论文情况&…

谈一谈QThread::CurrentThread和this->thread

QThread::CurrentThread是指的当前函数调用者者所在的线程 this->thread是指的当前对象所在的线程&#xff08;对象创建出来的时候所在的线程&#xff09; Qt文档说明 CurrentThread返回一个指向管理当前执行线程的QThread的指针 thread返回对象所在的线程 这两个函数所…

深度学习实验十一 卷积神经网络(2)——基于LeNet实现手写体数字识别实验

目录 一、数据 二、模型构建 三、模型训练及评价 四、打印参数量和计算量 五、模型预测 附&#xff1a;完整可运行代码 实验大致步骤&#xff1a; 一、数据 下载网站&#xff1a;MNIST数据集 之前的官网不能下载数据集了&#xff0c;403了&#xff0c;所以找到一个类似…

Python语法便捷查询

一、Python基础语法&#xff1a; (1)注释&#xff1a; (2)标识符&#xff1a; 简介&#xff1a;标识符的格式限制和C语言一样 (3)字符串定义方法&#xff1a; (4)字符串拼接&#xff1a; (5)字符串的格式化&#xff08;占位拼接&#xff09;&#xff1a; 和C语言的printf类…

Ansys Maxwell - 3PH 感应电机 - 第 2 部分 - 机床工具包 ACT

本篇博文是“Ansys Maxwell&#xff1a;3PH 感应电机 - 力和热耦合”的延续。在本篇博文中&#xff0c;我将展示如何使用 Ansys Machine Toolkit ACT 开发扭矩与速度曲线&#xff08;一系列性能曲线&#xff0c;包括效率图&#xff09;&#xff0c;以评估在 Ansys Maxwell 中建…

【含开题报告+文档+PPT+源码】基于springboot的教师评价系统的设计与实现

开题报告 随着信息技术的迅猛发展&#xff0c;教育信息化已成为现代教育的必然趋势。教研室作为高校教学管理的重要机构&#xff0c;肩负着提升教学质量、推动教学改革的重要使命。然而&#xff0c;传统的教学管理方式往往存在效率低下、数据分散、管理不便等问题&#xff0c;…

用 Python 从零开始创建神经网络(八):梯度、偏导数和链式法则

梯度、偏导数和链式法则 引言1. 偏导数2. 和的偏导数3. 乘法的偏导数4. Max 的偏导数5. 梯度&#xff08;The Gradient&#xff09;6. 链式法则&#xff08;The Chain Rule&#xff09; 引言 在我们继续编写我们的神经网络代码之前&#xff0c;最后两个需要解决的难题是梯度和…