Acwing342

ops/2024/11/19 11:51:07/

这个代码实现了一种结合 连通块分解拓扑排序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.ppmy.cn/ops/134960.html

相关文章

排序算法——快速排序

目录 一、快速排序的原理 二、快速排序的过程 三、代码的实现 四、代码的优化 总结 一、快速排序的原理 快速排序的思想是分治法&#xff0c;将一个大问题分割成几个小问题解决&#xff0c;首先选择一个数作为分水岭&#xff0c;然后让比该数大的都在它的右边&#xff0c…

【数据结构初阶】栈和队列的建立

栈 概念和结构 栈是一种特殊的线性表&#xff0c;它只允许一端进行插入和删除数据操作&#xff0c;这一端被称为栈顶&#xff0c;则另一端被称为栈底&#xff0c;而栈内的数据遵循后进后出&#xff0c;先进后出的原则 入栈&#xff1a;栈的插入操作被称为进栈、入栈、压栈&a…

blockchain实现遇到的问题

区块链分叉 v1114 : 基于python socket 创建TCP server&#xff0c;以中心化的形式暂时实现区块链的状态同步 C:\Users\vin0sen>nc 192.168.137.1 9000 Enter a new data: 111 {"index": 1, "timestamp": "2024-11-14 15:28:53.173112", &quo…

Shell脚本4 -- 数学运算

声明&#xff1a; 本文的学习内容来源于B站up主“泷羽sec”视频【shell &#xff08;3&#xff09;脚本参数传递与数学运算】的公开分享&#xff0c;所有内容仅限于网络安全技术的交流学习&#xff0c;不涉及任何侵犯版权或其他侵权意图。如有任何侵权问题&#xff0c;请联系本…

2025年入门深度学习或人工智能,该学PyTorch还是TensorFlow?

随着2025应用人工智能和深度学习技术的举世泛气&#xff0c;还在迷茫于该选择哪个深度学习框架吗&#xff1f;PyTorch和TensorFlow是并立于深度学习世界两座巨塔&#xff0c;但是越来越多人发现&#xff0c;在2025年&#xff0c;PyTorch似乎比TensorFlow更为流行和被接受。下面…

区块链智能合约开发:全面解析与实践指南

随着区块链技术的不断发展&#xff0c;智能合约作为其中的核心组成部分&#xff0c;已经在多个领域展现出了巨大的潜力。智能合约不仅是去中心化应用&#xff08;DApp&#xff09;和去中心化金融&#xff08;DeFi&#xff09;的基础&#xff0c;也是推动区块链技术应用广泛发展…

跨平台WPF框架Avalonia教程 十一

控件类型 如果您想创建自己的控件&#xff0c;Avalonia中有三个主要的控件类型。首先要做的是选择最适合您使用场景的控件类型。 用户控件(User Controls)​ UserControl是创建控件的最简单方法。这种类型的控件最适合特定于应用程序的“视图”或“页面”。UserControl的创建…

MATLAB深度学习(二)——如何训练一个卷积神经网路

2.1 基本概念 从数学的角度看&#xff0c;机器学习的目标是建立输入和输出的函数关系&#xff0c;相当于 y F&#xff08;x&#xff09;的过程。F&#xff08;x&#xff09;就是我们所说的模型&#xff0c;对于使用者来说&#xff0c;这个模型就是一个黑箱&#xff0c;我们不知…