分层图

· · 算法·理论

1. 什么是分层图

在某些图论问题中，有额外的维度信息需要维护，并且该维度对图的信息有变动。此时，我们可以将图复制若干份，每一份代表一“层”，不同“层”代表着不同的额外维度，并以此修改层内的图信息以及获得层间的连边信息。

分层图更多的是建图的思想，而不是一个具体的算法，所以具体怎么运用，需要在题目中总结。

2. 分层图例题1：飞行路线

可以复制 k 张图，第 i 张图表示还能跳 i-1 次。
将图复制 k 次，每一次可以选择在本层跳（不免费）或者跳下去（免费）。

3. 分层图例题2：Codevs 1391

由于网站不维护了，所以放出题面：

在幻想乡，伊吹萃香是能够控制物体密度的鬼王。因为能够控制密度，所以萃香能够制造白洞和黑洞，并可以随时改变它们。某一天萃香闲着无聊，在妖怪之山上设置了一些白洞或黑洞，由于引力的影响，给妖怪们带来了很大的麻烦。于是他们决定找出一条消耗体力最少的路，来方便进出。已知妖怪之山上有 N 个路口（编号1 .. N），每个路口都被萃香设置了一定质量白洞或者黑洞。原本在各个路口之间有 M 条单向路，走过每一条路需要消耗一定量的体力以及1个单位的时间。由于白洞和黑洞的存在，走过每条路需要消耗的体力也就产生了变化，假设一条道路两端路口黑白洞的质量差为 delta：

  1. 从有白洞的路口走向有黑洞的路口，消耗的体力值减少 delta，若该条路径消耗的体力值变为负数的话，取为 0。
  2. 从有黑洞的路口走向有白洞的路口，消耗的体力值增加 delta。
  3. 如果路口两端均为白洞或黑洞，消耗的体力值无变化。

由于光是放置黑洞白洞不足以体现萃香的强大，所以她决定每过 1 个单位时间，就把所有路口的白洞改成黑洞，黑洞改成白洞。当然在走的过程中你可以选择在一个路口上停留 1 个单位的时间，如果当前路口为白洞，则不消耗体力，否则消耗 s[i] 的体力。现在请你计算从路口 1 走到路口 N 最小的体力消耗。保证一定存在道路从路口 1 到路口 N。

N ≤ 5000 , M ≤ 30000

在单数秒和奇数秒时，两张图是明显不一样的。
所以建两张图，一张是在奇数秒时的图，另一张是偶数秒时的图。
每一次都要在两张图上跳。

4. 分层图例题3：动态图的最短路

一张图上，每走一步，所有的边权 x 变为 f(x)，其中：

f(x)=\dfrac{1}{1-x}

求最短路

因为边权变化如下：x\to \dfrac{1}{1-x}\to \dfrac{x-1}{x}\to x。考虑建三层图便可。