2020.04.04日常总结——分层图

$\color{green}{\text{分层图}}$分层图

• 所谓分层图，顾名思义，就是把一张图 $\color{red}{\text{复制}}$复制 成好几层，每一层都有属于自己层的特殊含义。

• 每层的图中的边权相同，表示从一个点到另一个点的边权。

• 分层图的核心是层间转移的代价的确定。一般而言，题目会给我们一些从一个点到另一个点的代价的“优惠”，而这些优惠，我们就通常让它作为层间边的边权。

• 最后一个需要注意的点的编号的确定。两种方法（记一层图有 $n$n 个点和 $m$m 条边）：

  1. 第 $i$i 层第 $j$j 个点编号成 $(i,j)$(i,j)，即二维的。
  2. 第 $i$i 层第 $j$j 个点编号成 $i \times n + j$i×n+j，即一维的。笔者就采用这种方法。

---

$\color{green}{\text{洛谷P4822\ \ \ \ \ [BJWC2012]冻结}}$洛谷P4822     [BJWC2012]冻结

$\color{blue}{\text{【简化题意】：}}$【简化题意】： 现在一个大陆上有 $N$N 个城市，$M$M 条双向的道路。城市编号为 $1 \cdots N$1⋯N，我们在 $1$1 号城市，需要到 $N$N 号城市，怎样才能最快地到达呢？

现在，我们一共有 $K$K 张可以使时间变慢 $50 \%$50% 的 SpellCard，也就是说，在通过某条路径时，我们可以选择使用一张卡片，这样，我们通过这一条道路的时间就可以减少到原先的一半。需要注意的是：

1. 在一条道路上最多只能使用一张 SpellCard。
2. 使用一张 SpellCard 只在一条道路上起作用。
3. 你不必使用完所有的 SpellCard。

对于 $100 \%$100% 的数据：$1 \leq K \leq N \leq 50，M \leq 1000$1≤K≤N≤50，M≤1000。

$\color{blue}{\text{【思路】：}}$【思路】： 我们建 $K+1$K+1 层的图（从第 $0$0 层编号至第 $K$K 层），第 $i$i 层图表示使用了 $i$i 张 SpellCard。

考虑如何连边，对于一条边 $(u,v,w)$(u,v,w)（某层的 $u$u 号点到该层的第 $v$v 号点有一条边权为 $w$w 的边），我们从每一层都连一条双向边 $(u,v,w)$(u,v,w)。

用 SpellCard 时如何连边呢？我们可以从每一层（记为第 $i$i 层）向上一层（即第 $i+1$i+1 层）连两条有向边 $(u,v',\dfrac{w}{2})$(u,v′,2w​) 和 $(v,u',\dfrac{w}{2})$(v,u′,2w​)，其中 $u',v'$u′,v′ 表示上一层的 $u,v$u,v 点。

建好图后，直接跑一般 dijkstra 算法即可。至于第一条规则，因为我们在一条边上走两遍（以上）肯定不优，所以第一条规则是无用的。

最后统计答案时，只需遍历每一层的第 $n$n 号点，取其最小值即可。注意！不一定第 $K$K 层是最优。可能出现最短路中边数不到 $K$K 条的情况。此时，第 $K$K 层的答案是反反复复走了某些边后得到的，反而比如其它层优！！！

一定注意点数和边数的问题。

$\color{blue}{\text{【代码】：}}$【代码】：

---

想要四倍经验吗？Come on！！！