首页 > 其他分享 >分层图

分层图

时间:2024-09-25 11:26:12浏览次数:8  
标签:决策 分层 时间 Delta dis mod

分层图

引入

我们发现,在某些最短路问题中,并不只有一种性质的边,或者说允许改变一些边权。为了处理这样的问题, 分层图建模思想 应运而生。

构建

对于这样的问题,我们考虑根据边的不同性质分别建图,在图的内部则是一些普通边,在图与图之间连上那些 “特殊的性质边”,换句话说,就是将 决策前的状态决策后的状态 之间连接一条 权值为决策代价 的边,表示付出该代价后就可以进行此步状态转移

决策,就是分层图的构图依据。

具体的实现有两种:

数组 建边 特点
方式一:物理构图 \(dis[N*K]\) 图内,图间 第 \(i\) 张图的起点是(i-1) * n+1
方式二:DP构图 \(dis[N][K]\) 只有图内,图间由dp决策代替 \(vis\) 也是二维,多一维模拟层数

例题

JLOI2011 飞行路线

经典题,\(k\) 层图,图之间有免费边。

CSP-J 2023 旅游巴士

关键是寻找分层依据。发现发车间隔 \(k\) 很小,考虑从它下手。假设当前时间为 \(p\), 走到了 \(u\) 点, 到 \(v\) 的边权为 \(w\)。

  • 若 \(p < w\), 没办法走。但其实如果在起点多等待几轮就可以通过了。设在多等的时间 \(\Delta t = \frac{\lceil w-p \rceil}{k} \times k\) ,因此真正的时间 \(t = \Delta t + p\)。
  • 若 \(p \ge w\),直接走就行。

怎么用 \(u\) 和 \(p\) 来转移呢?我们发现实际的时间并不重要,因为很大一部分多等的时间都可以用 \(k\) 的若干倍轻松统计。于是只需要关心 \(p \mod k\) 就可以啦!,不妨称其为 余数时间。那么定义就有了: \(f[i][j]\) 表示 当前在点 \(i\), 余数时间 为 \(j\) 的 实际时间 的最小值。

  • 若 \(p < w\), 有转移 \(dis[v][(p + 1) \mod k] = \min(dis[u][p \mod k], \ p) + 1\) 。
  • 若 \(p \ge w\),有转移 \(dis[v][(t + 1) \mod k] = \min(dis[u][t \mod k]+ \Delta t, \ t) + 1\) 。

边界条件: \(dis[1][0] = 0\)。

答案:\(dis[n][0]\)。

总结

个人更喜欢 DP建图, 因为它更突出了 “最短路算法本质是 \(dp\) 的运用”

参考博客

关于分层图(学了你不吃亏,学了你不上当 雾) - AcWing

图论-分层图详解(附完整代码) - c20251917_lzy - 博客园 (cnblogs.com)

Genius_Star - 题解:CSP-J 2023旅游巴士

标签:决策,分层,时间,Delta,dis,mod
From: https://www.cnblogs.com/superl61/p/18430951

相关文章

  • 【VMware ESXi】如何查看启用内存分层功能的 ESXi 主机使用了多少 NVMe 内存。
    VMwarevSphere8U3中作为技术预览所引入的功能“内存分层(MemoryTiering)”,相信大家已经在自己的测试或实验环境中应用并验证了,如果你还不知道,请跳转到这篇(把硬盘当内存用?VMware内存分层(MemoryTiering),你值得拥有!)文章了解相关介绍以及如何启用它。需要注意的是,目前在启用内存......
  • 蒙牛工厂智能化改造解决方案:分层联动的信息化+智能化工厂架构、构建智能工厂的物联网
    蒙牛工厂的智能化改造解决方案主要体现在分层联动的信息化+智能化工厂架构以及构建智能工厂的物联网大数据平台两大方面。以下是对这两方面的详细阐述: 一、分层联动的信息化+智能化工厂架构蒙牛工厂的智能化改造采用了分层联动的架构,这一架构主要包括计划层、执行层和控制层......
  • DDD分层架构
    DDD分层架构、整洁架构、六边形架构都是以领域模型为核心,实行分层架构。内部核心业务逻辑与外部应用、资源隔离并解耦。从而设计出“高内聚、低耦合”的微服务,以实现微服务的架构演进。DDD分层架构使得微服务的架构边界变得清晰。六边形架构提到微服务架构,一定会涉及到六......
  • 9章10节:用R实现分层随机化
    在临床试验和其他科学研究中,随机化是一种常见的分配方法,用于将研究对象随机分配到不同的处理组或对照组。这有助于消除潜在的混杂因素,确保研究结果的公正性。然而,在某些情况下,已知的协变量(如年龄、性别、疾病严重程度)可能对结果有显著影响。如果不加以控制,这些协变量可能会导......
  • 总结!计网分层 每层任务 每层协议
    总结!计网OSI七层模型及每层作用?每层协议有哪些?OSI七层模型是什么?每一层的作用是什么?应用层解决通过应用进程的交互来实现特定网络应用的问题表示层进行数据处理比如编码解码加密解密压缩和解压缩会话层管理应用进程之前的会话传输层解决进程之间基于网络......
  • 浅谈分层图
    分层图讲真的…感觉有点像那么一点点的种类并查集简单来说,就是把一个图分成很多层,然后对图进行一些处理比较模板一点的东西就是直接在分层图上跑最短路,这个时候就涉及到了很多决策,每一个决策能进行一些特殊的操作,比如让某条边免费(边权为0,不是把边切掉),让某条边花费减半之......
  • Linux字符设备驱动:分层/分离思想、总线设备驱动模型和设备树
    本文章参考韦东山嵌入式Linux应用开发完全手册......
  • 可测试,可维护,可移植:上位机软件分层设计的重要性
    互联网中,软件工程师岗位会分前端工程师,后端工程师。这是由于互联网软件规模庞大,从业人员众多。前后端分别根据各自需求发展不一样的技术栈。那么上位机软件呢?它规模小,通常一个人就能开发一个项目。它还有必要分前后端吗?有必要。本文从三个方面论述。分别是可测试,可维护,可移植。......
  • Docker 镜像的分层概念
    40.镜像的分层概念来更深入地理解镜像的概念‍镜像的分层镜像,是一种轻量级、可执行的独立软件包,它包含运行某个软件所需的所有内容,我们把应用程序和配置依赖打包好形成一个可交付的运行环境(包括代码、运行时需要的库、环境变量和配置文件等),这个打包好的运行环境就是image镜......
  • 三水的计算机网络学习之旅----实例探索如何来分层处理
    主机A要访问某个Web服务器1.首先在浏览器地址栏中输入Web服务器的域名,2.紧接着主机向Web服务器发送一个请求报文,3.服务器收到请求报文后执行相应操作,然后给主机发送响应报文4.主机收到响应报文后由浏览器负责解析与渲染。我们从五层原理体系来进行进一步解析:封装过程:(自......