一种特殊的建图方法，将原图复制 k 份，视为 k 个层，每层之间有一些额外的边连接。这样建立的图称为分层图。

许多题目，特别是当 k 很小的时候，可以使用分层图进行建模。

例题

LeetCode 3418

3418. 机器人可以获得的最大金币数 - 力扣（LeetCode）

传统的机器人捡金币 DP，金币值有负数，但允许机器人将至多 2 个格子变为 0

分层图板子题。

P4569 飞行路线

总结：（链接未公开）

题意：给定一个带权无向图和节点 u, v，可以选择 k 条边，将其边权变为 0（k \le 10），求操作后 u 到 v 的最短路。

CF-105059-C

https://codeforces.com/gym/105059/problem/C

题意：给定质数 g 和一个边权全为 1 的无向图，找出一条 1 到 n 路径（未必是简单路径），使得路径长度模 g 最小。只需输出路径长度模 g 的最小值。

显然当 g \ge 3 时，可以通过在两个点来回走，给路径长度不断 +2，凑成 g 的倍数，此时路径长度为 0。

当 g = 2 时，只需记录每个点是否有奇数长度路径和偶数长度路径即可，按奇偶构造一个分层图，对分层图进行 DFS 或 BFS 即可。