图论分层图
目录
【图论】分层图
一、分层图的核心思想
分层图是一种将图的不同状态拆分为多个“层”的建模方法，每层对应一种特定状态。通过这种方式，可以将复杂的状态转移问题转化为多层图中的最短路径问题。
核心特点：
- 层内边：表示普通操作（如正常行走）。
- 层间边：表示状态转移（如使用一次特殊能力、改变状态等）。
- 状态压缩：通常通过
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<>保证最小堆。