本篇随笔简单讲解一下图论中的分层图问题。
分层图，顾名思义就是分很多层的图。也就是类似二维数组，抽象地理解：不再是一个单一的平面图而是一个立体化的东西，不只有长宽，也有了自己的厚度——即为层数。
建立 多层 相同或相似的 图, 并在图与图之间进行连边，可以实现 两种性质的图 之间的 转移。或是 图与图 之间 有限制的转移。
用一道例题来理解一下：
约翰一共有 NN 个牧场.由 MM 条布满尘埃的小径连接。小径可以双向通行。每天早上约翰从牧场 11 出发到牧场 NN 去给奶牛检查身体。
通过每条小径都需要消耗一定的时间。约翰打算升级其中 KK 条小径，使之成为高速公路。在高速公路上的通行几乎是瞬间完成的，所以高速公路的通行时间为 00。
请帮助约翰决定对哪些小径进行升级，使他每天从 11 号牧场到第 NN 号牧场所花的时间最短。
在这道题中，会有一些边可以免费，我们考虑DP，但是发现并没有一个无后效性的转移方式。所以我们只能想其他的方式：建分层图。
建分层图感性来讲，就是：这种DP不是有后效性么？怎么变成无后效性的呢？直接每个状态我都来一张图！
假设免费建立k条边，所以就可以有k层图表示已经免费建立了1条边到免费建立了k条边 。注意，0层图也就是原图也是要建立的。
在连接每两个点的同时，将复制出来的另外k个图上对应的两个点连接起来。也将i图和j图上的对应的点连接起来。也就是让这条边权值为零的情况 。
所以就可以直接在上面跑最短路解决了。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/176680.html