分层图是什么（分层图是什么意思）



本篇随笔简单讲解一下图论中的分层图问题。

分层图，顾名思义就是分很多层的图。也就是类似二维数组，抽象地理解：不再是一个单一的平面图而是一个立体化的东西，不只有长宽，也有了自己的厚度——即为层数。

建立 多层 相同或相似的 图, 并在图与图之间进行连边，可以实现 两种性质的图 之间的 转移。或是 图与图 之间 有限制的转移。

用一道例题来理解一下：

约翰一共有 NN 个牧场.由 MM 条布满尘埃的小径连接。小径可以双向通行。每天早上约翰从牧场 11 出发到牧场 NN 去给奶牛检查身体。

通过每条小径都需要消耗一定的时间。约翰打算升级其中 KK 条小径，使之成为高速公路。在高速公路上的通行几乎是瞬间完成的，所以高速公路的通行时间为 00。

请帮助约翰决定对哪些小径进行升级，使他每天从 11 号牧场到第 NN 号牧场所花的时间最短。

在这道题中，会有一些边可以免费，我们考虑DP，但是发现并没有一个无后效性的转移方式。所以我们只能想其他的方式：建分层图。

建分层图感性来讲，就是：这种DP不是有后效性么？怎么变成无后效性的呢？直接每个状态我都来一张图！

假设免费建立k条边，所以就可以有k层图表示已经免费建立了1条边到免费建立了k条边 。注意，0层图也就是原图也是要建立的。

在连接每两个点的同时，将复制出来的另外k个图上对应的两个点连接起来。也将i图和j图上的对应的点连接起来。也就是让这条边权值为零的情况 。

所以就可以直接在上面跑最短路解决了。

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/bcyy/23067.html