一、分层图的核心思想
分层图是一种将图的不同状态拆分为多个“层”的建模方法，每层对应一种特定状态。通过这种方式，可以将复杂的状态转移问题转化为多层图中的最短路径问题。
核心特点：
- 层内边：表示普通操作（如正常行走）。
- 层间边：表示状态转移（如使用一次特殊能力、改变状态等）。
- 状态压缩：通常通过
j * n + u的方式编号节点（j表示层数，u是原图节点）。
二、分层图的构建方法
-
物理构图
- 定义：直接将图复制为
k层，每层节点数为n。 - 层内边：与原图相同，边权不变。
- 层间边：按状态转移规则添加（如使用一次特殊能力）。
- 适用场景：
k较小（如k ≤ 10）。 - 缺点：空间消耗大（总节点数为
k * n）。
- 定义：直接将图复制为
-
DP 构图
- 定义：通过动态规划模拟状态转移，无需显式构建多层图。
- 状态表示：使用二维数组
dis[u][j]表示在节点u、状态j下的最短距离。 - 适用场景：状态维度较大的问题（如时间、钥匙状态等）。
- 优点：节省空间，适合高维状态。
三、分层图的典型应用场景
-
有限次决策
- 例题：允许最多使用
k次特殊能力（如免费边、升级等）。 - 建模：构建
k+1层图，层间边表示使用能力。
- 例题：允许最多使用
-
状态依赖
- 例题：钥匙状态、时间余数、奇偶性等。
- 建模：根据状态分层（如钥匙状态用二进制编码）。
-
多维状态转移
- 例题：同时考虑时间、资源、权限等状态。
- 建模：每个维度对应一层，组合成多维分层图。
四、分层图的详细例题与实现
例题 1：JLOI2011 飞行路线（允许 k 次免费边）
问题描述：
给定一个无向图，最多可以选择 k 条边免费，求从起点到终点的最短路径。
分层图建模：
- 构建
k+1层图（0~k 层）。 - 层内边：原图边权不变。
- 层间边：从第
j层的u到第j+1层的v，边权为 0（表示使用一次免费机会）。
C++ 实现：
#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10, M = 1e6 + 10;
int h[N * 10], e[M * 2], ne[M * 2], w[M * 2], idx;
bool st[N * 10];
int dis[N * 10];void add(int a, int b, int c) {e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}void dijkstra(int n, int k) {priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;memset(dis, 0x3f, sizeof dis);dis[1] = 0;pq.push({0, 1});while (pq.size()) {auto [d, u] = pq.top();pq.pop();if (st[u]) continue;st[u] = true;for (int i = h[u]; ~i; i = ne[i]) {int v = e[i], cost = w[i];if (dis[v] > d + cost) {dis[v] = d + cost;pq.push({dis[v], v});}}}
}int main() {int n, m, k;cin >> n >> m >> k;memset(h, -1, sizeof h);for (int i = 0; i < m; i++) {int a, b, c;cin >> a >> b >> c;for (int j = 0; j <= k; j++) {int u = a + j * n, v = b + j * n;add(u, v, c), add(v, u, c); // 层内边if (j < k) {int u2 = a + (j + 1) * n, v2 = b + (j + 1) * n;add(u, v2, 0), add(v, u2, 0); // 层间免费边add(v, v2, 0), add(u, u2, 0);}}}dijkstra(n, k);int res = 0x3f3f3f3f;for (int j = 0; j <= k; j++) {res = min(res, dis[n + j * n]);}cout << res << endl;return 0;
}
关键点：
- 节点编号：
u + j * n表示第j层的节点u。 - 层间边：允许最多
k次免费升级，边权为 0。
例题 2：CSP-J 2023 旅游巴士（时间余数分层）
问题描述：
给定发车间隔 k，求从起点到终点的最短时间（允许等待多轮车次）。
分层图建模：
- 按时间余数
t % k分层，共k层。 - 状态
(u, t % k)：表示当前在节点u，时间余数为t % k。 - 边权动态调整：根据当前时间和发车间隔
k计算等待时间。
C++ 实现：
#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10, K = 1e3 + 10;
int h[N], e[N * 2], ne[N * 2], w[N * 2], idx;
int dis[N][K]; // dis[u][j]: 节点u，余数j的最短时间void add(int a, int b, int c) {e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}void dijkstra(int n, int k) {priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;memset(dis, 0x3f, sizeof dis);dis[1][0] = 0;pq.push({0, 1, 0});while (!pq.empty()) {auto [d, u, t_mod] = pq.top();pq.pop();if (d > dis[u][t_mod]) continue;for (int i = h[u]; ~i; i = ne[i]) {int v = e[i], cost = w[i];int current_time = d;if (current_time < cost) {// 需要等待int delta = ((cost - current_time + k - 1) / k) * k;int new_time = current_time + delta;int new_mod = new_time % k;if (dis[v][new_mod] > new_time) {dis[v][new_mod] = new_time;pq.push({new_time, v, new_mod});}} else {// 直接走int new_time = current_time + 1;int new_mod = new_time % k;if (dis[v][new_mod] > new_time) {dis[v][new_mod] = new_time;pq.push({new_time, v, new_mod});}}}}
}int main() {int n, m, k;cin >> n >> m >> k;memset(h, -1, sizeof h);for (int i = 0; i < m; i++) {int a, b, c;cin >> a >> b >> c;add(a, b, c), add(b, a, c);}dijkstra(n, k);int res = 0x3f3f3f3f;for (int j = 0; j < k; j++) {res = min(res, dis[n][j]);}cout << res << endl;return 0;
}
关键点：
- 状态压缩：
dis[u][j]表示节点u在余数j下的最短时间。 - 动态调整时间：根据当前时间和发车间隔
k计算等待时间。
五、分层图的扩展应用
例题 3：孤岛营救问题（钥匙状态分层）
问题描述：
网格图中，门需要钥匙开启，钥匙分布在格子中，求从起点到终点的最短路径。
分层图建模：
- 钥匙状态：用二进制表示钥匙状态（如
101表示有钥匙 1 和 3）。 - 层内边：普通移动（墙或门未解锁时无法通过）。
- 层间边：拾取钥匙后状态转移。
C++ 实现（逻辑构图）：
#include <bits/stdc++.h>
using namespace std;const int N = 11, M = 100;
int h[M], e[M], ne[M], w[M], idx;
int dis[M][1 << 10]; // dis[u][state]: 节点u，钥匙状态state的最短距离void add(int a, int b, int c) {e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}void bfs(int n, int m, int p) {queue<pair<int, int>> q;memset(dis, 0x3f, sizeof dis);dis[0][0] = 0; // 起点(0,0)，无钥匙q.push({0, 0});while (!q.empty()) {auto [u, state] = q.front();q.pop();for (int i = h[u]; ~i; i = ne[i]) {int v = e[i], cost = w[i];int new_state = state;// 检查是否需要钥匙if (需要钥匙) {if (state 有钥匙) {new_state = state | 钥匙状态;} else {continue; // 无法通过}}if (dis[v][new_state] > dis[u][state] + cost) {dis[v][new_state] = dis[u][state] + cost;q.push({v, new_state});}}}
}
六、分层图的优化技巧
-
空间优化
- 物理构图：总节点数为
k * n，边数为k * m + ...。 - DP 构图：状态数为
n * 2^p（p为钥匙种类数）。
- 物理构图：总节点数为
-
时间优化
- 使用 01BFS（边权为 0 或 1 时）。
- 使用 优先队列优化的 Dijkstra（边权任意值）。
-
状态压缩
- 对于钥匙状态，用二进制位压缩。
- 对于时间余数，用
t % k表示。
七、分层图的适用场景总结
| 场景类型 | 示例问题 | 分层依据 | 构图方式 |
|---|---|---|---|
| 有限次决策 | 免费边、升级 | 使用次数 | 物理构图 |
| 状态依赖 | 钥匙、时间余数 | 钥匙状态、余数 | DP 构图 |
| 多维状态转移 | 资源、权限 | 组合状态 | DP 构图 |
八、分层图的常见错误与调试
- 节点编号错误：确保
u + j * n正确映射层和节点。 - 层间边方向错误：层间边应单向（如从
j层到j+1层）。 - 初始化错误：
dis数组未初始化为最大值。 - 优先队列优先级错误：使用
greater<>保证最小堆。
)
)
)
