分层图（建模思想）

Constant

·

2020-02-13 22:31:07

·

个人记录

1.什么是分层图

分层图最短路是指在可以进行分层图的图上解决最短路问题。

分层图：可以理解为有多个平行的图。

一般模型是：

在一个正常的图上可以进行 k 次决策

对于每次决策，不影响图的结构，只影响目前的状态或代价。

一般将决策前的状态和决策后的状态之间连接一条权值为决策代价的边，表示付出该代价后就可以转换状态了。

举个例子，如这个分层图

如图，在第一层（原图）中，2–3的权值为100，但是同时，我们向第二层的3号连了一条0权值的边，相当于，我们省去了100的权值，也走到了3号，对应了原题中K次免费操作中的一次。

每向下一层，对应一次免费操作，也就是说：

将对边权有影响的各种决策，转化为一个层次的图向另一个层次的图的转化

这就是分层图

（PS：关于层次，可以理解为不同的状态的图，例如本题对于K次免费决策，把决策1~K次都建立一层图）

2.分层图的应用范围

分层图可以使用在对图的边权有一定影响（如免费边，降低边权），已经图会随着时间变化的问题

并且这些影响的次数不能太多，一般地，我们有K次影响就要建立K层图

3.分层图的作用以及意义

我们先来看一道例题：

【JLOI2011】 飞行路线

Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务，设这些城市分别标记为0到n-1，一共有m种航线，每种航线连接两个城市，并且航线有一定的价格。Alice和Bob现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多k种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少？

分层图中的边权可以随着题目的改变而具备不同的意义。在本题中，边权的定义是：

若边（u,v,w)位于第i层图（起点与终点同层），表示已经免费了i-1条边，从u到v花费w。

若边(u,v,0 ）于i~i+1层（不同层，也就是说这条边代表一次免费操作），表示已经免费i-1条边，从u到v花费0（到达下一层）

似乎看起来很有道理，可答案是什么呢

由于本题求的是1到n的最短路，由于1到n能改建0到k中的任意次道路，再联系定义，得：

ans=MIn(dis[i]) ,i=0~k

最短路的数组大小要开max(k)*max(n)（因为K层图，每层N个点）

4.总结：

基本思想：建立K+1层图

有边的两个点，多建一条到下一层边权为0的单向边，如果走了这条边就表示用了一次机会

最后的答案去每层图目标点的最小值