多层图可以运用在最短路的一些问题上.是最短路的一种题型.本篇从题目入手进行分析.
前置只是:邻接表,最短路算法(最好使用Dijkstra)
多层图作为最短路算法的一种题型,主要操作集中在输入上.(输入时,在vector中建多层图)
P4568 [JLOI2011] 飞行路线 (洛谷)
大致题意不太想分析...
本题重点在于:可以免费在最多k种航线上搭乘飞机
多层图在此处的体现是建立k+1层图,并进行最短路(dij).
*此处的k是上文提到的"免费的k种航线"
这里k+1层图分为两个部分:
1.第一层图:题目给出的数据本身就是一层图,以样例为例:
(这里点2到点3之间的距离直接取最小值)
2.剩下的k层图:
(这里的k为1,所以本来应该只有1层图,因后续讲解需要将其与第一层图话在一起)
多层图,顾名思义,有很多层,在这道题目中,总共需要建k+1层,而第二部分中的k层,题目中没有直接给出,而是需要自己建的.
这里建图的代码是这样的:
建图有两个部分:
1.建立本层(第j层)
2.建立本层和下层的练习(第j层和第j层的联系)
因为输入是一条边一条边输入的,所以这两个部分在每次输入一条边时,都需要进行.
而且,建图过程中有一些需要注意的
(配合代码一起理解)
比如说,建立本层时的代码:
它的在邻接表中的下标 : a + j * n
其 j * n 的 j 就是第 j 层的意思(这边的层数的范围是是 0 - k )
可以配合上文给出的图片一起理解建图代码.
再比如说,这边建立本层和下层的连接的代码:
这个连接边的权值为0(代表了免费航线)