Acwing341

核心任务是通过两次 SPFA(Shortest Path Faster Algorithm) 算法计算一个图中从起点到终点路径上的 最小值最大值,并寻找节点划分使得 最大值 − 最小值 \text{最大值} - \text{最小值} 最大值最小值 的差值最大。

以下是逐步的详细讲解:


问题描述

输入:
  • 一个带权有向图,包含 n n n 个节点和 m m m 条边。
  • 每个节点有一个权值 w [ i ] w[i] w[i]
  • 边的方向和连接方式通过输入指定,可能是单向边或双向边。
输出:
  • 求一个节点划分,使得从起点 1 1 1 到终点 n n n 的路径上,经过所有点的最小值与反向路径上所有点的最大值之间的差值最大。

算法核心思想

  1. 计算两条路径的最值

    • 路径 1(正向路径):从起点 1 1 1 出发到图中每个点,找到从起点到达每个节点的最小权值(路径上节点的权值最小值)。
    • 路径 2(反向路径):从终点 n n n 出发,找到从终点到每个节点的最大权值(路径上节点的权值最大值)。
  2. 枚举分界点

    • 设某个节点 i i i 是划分点,则路径 1 的最小值为 dmin[i],路径 2 的最大值为 dmax[i]
    • 计算 差值 = d m a x [ i ] − d m i n [ i ] \text{差值} = dmax[i] - dmin[i] 差值=dmax[i]dmin[i] 并求取最大差值。

代码逐步解析

1. 数据结构与变量定义
const int N = 100010, M = 2000010;
int n, m;
int w[N]; // 每个节点的权值
int hs[N], ht[N], e[M], ne[M], idx; // 邻接表存储正向图和反向图
int dmin[N], dmax[N]; // 从起点出发的最小值数组 & 从终点出发的最大值数组
bool st[N]; // 标记节点是否在队列中
queue<int> q; // 队列,用于 SPFA
  1. 邻接表

    • hs:存储正向图(起点到终点的路径)。
    • ht:存储反向图(终点到起点的路径)。
    • ene:链式前向星实现邻接表。
  2. 路径权值

    • dmin[i]:从起点到节点 i i i 的路径上最小的节点权值。
    • dmax[i]:从终点到节点 i i i 的路径上最大的节点权值。

2. 图的构建
void add(int h[], int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
  • 利用链式前向星存储边,分别存储在 hsht 两个邻接表中。
  • 对于每条边,根据输入决定是单向边还是双向边:
    add(hs, a, b), add(ht, b, a);
    if (c == 2) add(hs, b, a), add(ht, a, b); // 双向边
    

3. SPFA 算法
void spfa(int h[], int dist[], int type) {if (type == 0) { // 求最小值memset(dist, 0x3f, sizeof dmin);dist[1] = w[1]; // 起点权值q.push(1);} else { // 求最大值memset(dist, -0x3f, sizeof dmax);dist[n] = w[n]; // 终点权值q.push(n);}while (q.size()) {int t = q.front();q.pop();st[t] = false;for (int i = h[t]; ~i; i = ne[i]) {int j = e[i];if (type == 0 && dist[j] > min(dist[t], w[j]) || type == 1 && dist[j] < max(dist[t], w[j])) {if (type == 0) dist[j] = min(dist[t], w[j]); // 更新最小值else dist[j] = max(dist[t], w[j]); // 更新最大值if (!st[j]) {q.push(j);st[j] = true;}}}}
}
  • 初始化

    • 对于正向路径,初始化 dmin,起点的初始值为起点权值 w[1]
    • 对于反向路径,初始化 dmax,终点的初始值为终点权值 w[n]
  • 松弛操作

    • 对每条边进行松弛,根据路径类型(最小值或最大值)更新 dist[j]
  • 入队与出队

    • 如果节点的路径值被更新,则将节点加入队列。

4. 主算法
spfa(hs, dmin, 0); // 正向路径的最小值
spfa(ht, dmax, 1); // 反向路径的最大值// 枚举所有节点作为分界点,求最大差值
int res = 0;
for (int i = 1; i <= n; i++) res = max(res, dmax[i] - dmin[i]);cout << res << endl;
  • 调用两次 SPFA:

    1. spfa(hs, dmin, 0):计算从起点到每个节点的最小值。
    2. spfa(ht, dmax, 1):计算从终点到每个节点的最大值。
  • 枚举所有节点 i i i,计算 d m a x [ i ] − d m i n [ i ] dmax[i] - dmin[i] dmax[i]dmin[i] 并更新结果。


算法流程总结

  1. 构建正向图和反向图

    • 利用链式前向星存储普通边和特殊边。
  2. 正向路径的最小值计算

    • 通过 SPFA 从起点 1 1 1 计算到每个节点的路径最小值。
  3. 反向路径的最大值计算

    • 通过 SPFA 从终点 n n n 计算到每个节点的路径最大值。
  4. 枚举分界点

    • 对于每个节点 i i i,计算 d m a x [ i ] − d m i n [ i ] dmax[i] - dmin[i] dmax[i]dmin[i],并输出最大值。

时间复杂度

  1. 图的构建: O ( M ) O(M) O(M)
  2. 两次 SPFA: O ( M ) O(M) O(M)(每条边最多入队一次)。
  3. 枚举分界点: O ( N ) O(N) O(N)

总复杂度: O ( M + N ) O(M + N) O(M+N)


输出示例

输入:
5 6
1 2 3 4 5
1 2 0
2 3 0
3 4 0
4 5 0
5 3 2
3 1 2
输出:
4
解释:
  • 正向路径的最小值:dmin = [1, 2, 2, 2, 2]
  • 反向路径的最大值:dmax = [5, 5, 5, 5, 4]
  • 差值 d m a x [ i ] − d m i n [ i ] dmax[i] - dmin[i] dmax[i]dmin[i] 的最大值为 4 4 4

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

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

相关文章

⽂件内容的读写

文件 InputStream &#xff08;字节流读出 抽象类&#xff09; InputStream 只是⼀个抽象类&#xff0c;要使⽤还需要具体的实现类 FileInputStream&#xff08;字节流读出&#xff09; OutputStream&#xff08;字节流写入&#xff09; Reader&#xff08;字符流读入&#xff…

FreeRTOS消息队列实验与出现的问题

目录 实验名字&#xff1a;队列操作实验 1、实验目的 2、实验设计 3、实验工程 4、实验程序与分析 ●任务设置 ● 其他应用函数 ● main()函数 ● 任务函数 ●中断初始化及处理过程 5.程序运行结果分析 6.进行实验移植时所遇到的问题 1.项目中mymalloc等函数缺少 …

el-cascader 使用笔记

1.效果 2.官网 https://element.eleme.cn/#/zh-CN/component/cascader 3.动态加载&#xff08;官网&#xff09; <el-cascader :props"props"></el-cascader><script>let id 0;export default {data() {return {props: {lazy: true,lazyLoad (…

Linux之进程概念(2)

Linux之进程概念&#xff08;2&#xff09; 孤儿进程 父进程如果提前退出&#xff0c;那么子进程后退出&#xff0c;进入Z之后&#xff0c;那该如何处理呢&#xff1f; 父进程先退出&#xff0c;子进程就称之为“孤儿进程” 孤儿进程被1号init进程领养&#xff0c;当然要有in…

1+X应急响应(网络)日志分析:

日志分析&#xff1a; Web日志分析&#xff1a; http协议&#xff1a; http版本演变&#xff1a; http协议工作原理&#xff1a; http协议的特点&#xff1a; http请求报文&#xff1a; http请求方法&#xff1a; http响应报文&#xff1a; UserId&#xff1a;注册网站的序列号…

go-zero(二) api语法和goctl应用

go-zero api语法和goctl应用 在实际开发中&#xff0c;我们更倾向于使用 goctl 来快速生成代码。 goctl 可以根据 api快速生成代码模板&#xff0c;包括模型、逻辑、处理器、路由等&#xff0c;大幅提高开发效率。 一、构建api demo 现在我们通过 goctl 创建一个最小化的 HT…

计算机编程中的设计模式及其在简化复杂系统设计中的应用

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 计算机编程中的设计模式及其在简化复杂系统设计中的应用 计算机编程中的设计模式及其在简化复杂系统设计中的应用 计算机编程中的…

latex中,两个相邻的表格,怎样留一定的空白

目录 问题描述 问题解决 问题描述 在使用latex写论文时&#xff0c;经常表格需要置顶写&#xff0c;则会出现两个表格连在一起的情况。下一个表名容易与上面的横线相连&#xff0c;如何通过明令&#xff0c;留出一定的空白。 问题解决 在第二个表格的 \centering命令之后…

leetcode01——合并两个有序数组

0.本题学到的知识 1.python的操作中&#xff0c;哪些是在原数据上进行操作的&#xff1f; 新开辟的行为&#xff1a;list1list1[m:n] 原数据&#xff1a;list1[a:b]list1[m:n] 新开辟&#xff1a;list1list1list2 原数据&#xff1a;list1.append(list2[i]); list1.extend(list…

深度学习的艺术:揭秘卷积神经网络(CNN)的神秘面纱

深度学习的艺术&#xff1a;揭秘卷积神经网络&#xff08;CNN&#xff09;的神秘面纱 一、CNN的构成要素二、CNN的工作流程三、CNN的应用领域四、CNN的优势与局限 #引言&#xff1a; 在人工智能的璀璨星空中&#xff0c;卷积神经网络&#xff08;CNN&#xff09;如同一颗耀眼的…

Linux高阶——1116—环形队列生产者消费者

目录 1、环形队列 2、生产者消费者 环形队列数组实现代码 成功截图 1、环形队列 相比于线性队列&#xff0c;环形队列可以有效避免访问越界问题&#xff0c;使用下标访问队列元素时&#xff0c;到达末尾后下标归0&#xff0c;返回起始位置&#xff0c;使用下标运算即可 a…

学习大数据DAY61 宽表加工

目录 模型设计 加工宽表 任务调度&#xff1a; 大表 - 把很多数据整合起来 方便后续的明细查询和指标计算 模型设计 设计 建模 设计: excel 文档去编写 建模: 使用建模工具 PowerDesigner Navicat 在线画图工具... 把表结构给绘 制出来 共享\项目课工具\pd 加工宽表 数…

DBeaver MACOS 安装 并连接到docker安装的mysql

官网下载&#xff1a;Download | DBeaver Community 网盘下载&#xff1a;链接: https://pan.baidu.com/s/15fAhbflHO-AGc-uAnc3Rjw?pwdbrz9 提取码: brz9 下载驱动 连接测试 报错 null, message from server: "Host 172.17.0.1 is not allowed to connect to this M…

24首届数证杯(流量分析部分)

目录 流量分析 流量分析 1、分析网络流量包检材&#xff0c;写出抓取该流量包时所花费的秒数?(填写数字&#xff0c;答案格式:10) 3504相加即可 2、分析网络流量包检材&#xff0c;抓取该流量包时使用计算机操作系统的build版本是多少? 23F793、分析网络流量包检材&#x…

云服务器ECS经济型e实例和通用算力u1实例有啥区别?

阿里云服务器ECS经济型e实例怎么样&#xff1f;对比ECS通用算力型u1实例哪个更好&#xff1f;u1实例更好。阿里云服务器网aliyunfuwuqi.com二者均为云服务器ECS的实例规格&#xff0c;e实例是共享型云服务器&#xff0c;u1实例是独享型云服务器&#xff0c;何为共享&#xff1f…

QT中使用图表之QChart绘制柱状图

绘制条形&#xff08;柱状&#xff09;图&#xff0c;系列选择条形系列QBarSeries x轴选择条形图的种类轴QBarCategoryAxis 1、创建图表视图 //1、创建图表视图 QChartView * view new QChartView(this); //开启抗锯齿 view -> setRenderHint(QPainter::Antialiasing); …

Essential Cell Biology--Fifth Edition--Chapter one (8)

1.1.4.6 The Cytoskeleton [细胞骨架] Is Responsible for Directed Cell Movements 细胞质基液不仅仅是一种无结构的化学物质和细胞器的混合物[soup]。在电子显微镜下&#xff0c;我们可以看到真核细胞的细胞质基液是由长而细的丝交叉而成的。通常[Frequently]&#xff0c;可…

【Linux】守护进程

目录 进程组 会话 作业控制 实现守护进程 我们在写完一些网络服务后&#xff0c;如果想让这个服务一直在云服务器的后台运行着&#xff0c;那该如何实现呢&#xff1f;其实就用到了这篇博客要讲的守护进程 进程组 我们首先需要了解进程组的概念&#xff0c;其实sleep 1000这…

nginx.conf配置文件中的命令

打开我们的conf文件 nginx.conf文件中&#xff0c;分为3大块&#xff1a; 全局块&#xff0c;就是events和http块之外的内容。设置nginx服务器整体运行的指令 格式为&#xff1a; 指令名 指令值 events块&#xff0c;用于配置与用户的网络连接的内容&#xff0c;对nginx的…

51单片机基础07 实时时钟-思路及代码参考1

目录 一、实现功能 二、思路1的分析 1、定时器0 2、外部中断0 3、主函数main 4、其他重要功能函数 一、实现功能 1、实现最基本的计时功能&#xff0c;显示时、分、秒&#xff0c;可以通过按键设置时间。 要求&#xff1a;时钟计时精确&#xff0c;按键操作不影响计时。…