分层图

介绍

动态规划思想在图论中的一种应用。当有额外的状态维度（或约束条件）时，在每个状态下建一张图，并设计不同层间的转移关系。

• 层内边：同一个状态层内，在图节点之间转移
• 层间边：在不同状态层之间转移

可视化

实现

显式分层

数组多开一个层维度

struct Next{
    int layer; // 层
    int next; // 下一个节点
    int weight; // 边权
};
// 邻接表
vector<vector<vector<Next>>> adj;
// 访问第 k 层上节点 u 的所有出边 v
for(auto &v: adj[k][u]){...}

层编码

第 $k$ 层上节点 $u$ 表示为 $k \times n + u$， $n$ 是每层节点数

struct Next{
    int next; // 下一个节点
    int weight; // 边权
};
// 邻接表
vector<vector<Next>> adj;
// 访问第 k 层上节点 u 的所有出边 v
for(auto &v: adj[u + k * n]){...}

应用

豁免边

可以在转移时将边权视为 $0$ 最多 $k$ 次，求最短路

• 第 $i$ 层表示剩余 $i$ 次豁免机会
• 对于路径 $u_i \to v_i$，建立权值为 $0$ 的边 $u_i \to v_{i-1}$
• 在分层图上用最短路算法

多模式切换

可以在 $k$ 种模式中切换，切换模式有额外权值 $T$

• 第 $i$ 层表示第 $i$ 种模式
• 对于节点 $u_i$，建立权值为 $T$ 的边 $u_i \to u_j, j \in [0, k]$

逆向边

可以按有向边的反向转移最多 $k$ 次

• 第 $i$ 层表示剩余 $i$ 次逆向转移机会
• 对于路径 $u_i \to v_i$（权值$w$），建立权值为 $w$ 的边 $v_i \to u_{i-1}$

复杂度

• 点数：$O(nk)$
• 边数：$O(m_{层内}k + m_{层间})$