当前位置: 首页 > news >正文

分层图

分层图:可以理解为有多个平行的图。

适用场景:题目对边的权值提供可选的操作,比如可以将一定数量的边权减半
一般模型是:在一个正常的图上可以进行 k 次决策,对于每次决策,不影响图的结构,只影响目前的状态或代价。一般将决策前的状态和决策后的状态之间连接一条权值为决策代价的边,表示付出该代价后就可以转换状态了。

对于分层图的构建步骤可以描述为:
1、先将图复制成 k+1 份 (0 ~ k)
2、对于图中的每一条边 <u,v> 从 ui 到 vi+1 建立与题目所给操作相对应的边(i=0,1,…,k)

k代表了进行操作的次数,而每层之间点的关系代表了何时进行操作。

例如:有带权边 <u,v> = w, 可选操作:修改权值为0
让第 i 层的点 u 向 i+1 层的点 v连一条边权为 0 的边。

一般有两种方法解决分层图最短路问题:
建图时直接建成k+1层。
我们建k+1层图。然后有边的两个点,多建一条到下一层边权为0的单向边,如果走了这条边就表示用了一次机会
有N个点时,1n表示第一层,(1+n)(n+n)代表第二层,(1+2n)(n+2*n)代表第三层,(1+i*n)(n+in)代表第i+1层。因为要建K+1层图,数组要开到n * ( k + 1),点的个数也为n * ( k + 1 ) 。

多开一维记录机会信息
我们把dis数组和vis数组多开一维记录k次机会的信息。

dis[ i ][ j ] 代表到达 i 用了 j 次免费机会的最小花费.
vis[ i ][ j ] 代表到达 i 用了 j 次免费机会的情况是否出现过.
更新的时候先更新同层之间(即花费免费机会相同)的最短路,然后更新从该层到下一层(即再花费一次免费机会)的最短路。

时间复杂度:O(k*(m+n)log(n))

http://www.hskmm.com/?act=detail&tid=35343

相关文章:

  • 10.20总结
  • 学习相关
  • 题解:Luogu P10644 [NordicOI 2022] 能源网格 Power Grid
  • 题解:Luogu P10004 [集训队互测 2023] Permutation Counting 2
  • 题解:Luogu P2075 区间 LIS
  • 英语_阅读_2050 Space tourism_待读
  • goframe框架命令行工具gf在zsh下不能用
  • 题解:Luogu P4143 采集矿石
  • 从18w到1600w播放量,我的一点思考。
  • 扣一个细节问题
  • 10.20java作业
  • 题解:Luogu P14175 【MX-X23-T5】向死存魏
  • 题解:Luogu P14254 分割(divide)
  • 题解:Luogu P6898 [ICPC 2014 WF] Metal Processing Plant
  • 20251020
  • 32-腾讯IM接入资料和定价
  • 题解:AtCoder ARC207A Affinity for Artifacts
  • 构造单
  • [笔记]高斯消元
  • 半导体设备各细分领域的国内外龙头公司
  • CSP-S 34
  • 02.Python百行代码实现抽奖系统
  • CSP-S 35
  • CSP-S 29
  • 2025网络安全振兴杯wp
  • 10.20每日总结
  • CSP-S 31
  • 后缀树
  • ES原理、zookeeper、kafka
  • CF1606E Arena 题解(动态规划)