目录
- 分层图（Layered Graph）
- 简介
- 思想
- 实现
- 暴力建图
- DP思想
- 例题
- [ABC395E] Flip Edge
- 例题列表
- 坑
分层图（Layered Graph）
简介
简单来说，如果你发现最短路问题中多了几个“特殊条件”（比如有 \(K\) 次免费机会、或者有 \(K\) 次翻倍机会），这就是分层图的用武之地。
思想
传统的图论节点通常只表示“位置”。但在分层图中，一个节点表示的是 (当前位置, 剩余机会/当前状态)。
- 普通图： 节点 \(u\) 表示你在城市 \(u\)。
- 分层图： 节点 \((u, k)\) 表示你在城市 \(u\)，且你已经使用了 \(k\) 次特殊机会。
实现
有两种常用方法：
暴力建图
直接在内存里建出 \(K+1\) 层图。
层内边： 每一层内部按照原图建边，权重不变。表示正常走。
层间边： 从第 \(i\) 层的 \(u\) 连向第 \(i+1\) 层的 \(v\)。权重设为“特殊代价”（如 0 或 原重的一半）。表示“消耗一次机会”。
终点： 最终结果通常是 \(\min(dist[target][0...K])\)。
DP思想
不需要真的把图画出来，而是在跑 Dijkstra 时增加一个维度。
- 定义
dist[u][k]为到达 \(u\) 点且用了 \(k\) 次机会的最短路。 - 转移 1：
dist[v][k] = dist[u][k] + weight（正常走） - 转移 2：
dist[v][k+1] = dist[u][k] + 0（用机会）
当然，也是需要具体问题具体分析，就比如下面这道题
例题
[ABC395E] Flip Edge
有两种操作！！！
- 移动操作：从当前顶点沿边移动到相邻顶点，成本为 1。具体来说，设当前顶点为 v，选择一条从 v 指向 u 的边，移动到顶点 u。
- 翻转操作：反转所有边的方向，成本为 X。具体来说，在操作前存在的每条从 v 到 u 的边，在操作后将变为从 u 到 v 的边，反之亦然。
问最小总成本
这道题可以只建双层图
一个是正图，一个是反图
可以花\(X\)的花费更换图
就可以了qwq
代码：
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
int main()
{int N, M;long long X;cin >> N >> M >> X;vector<vector<pair<int, int>>> g(2 * N);for (int i = 0; i < N; i++)g[i].push_back({i + N, X}), g[i + N].push_back({i, X}); // 双层图for (int i = 0; i < M; i++){int u, v;cin >> u >> v;u--; // 0-indexv--;g[u].push_back({v, 1});g[v + N].push_back({u + N, 1});}vector<long long> d(2 * N, INF);// dijkstrapriority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;d[0] = 0;pq.push({0, 0});while (!pq.empty()){auto [dist, u] = pq.top();pq.pop();if (dist > d[u])continue;for (auto [v, w] : g[u])if (d[v] > dist + w)d[v] = dist + w, pq.push({d[v], v});}long long ans = min(d[N - 1], d[2 * N - 1]);cout << ans << endl;
}
例题列表
其他的例题挂个列表吧
| name | from | 芝士点 |
|---|---|---|
| [JLOI2011] 飞行路线 | 洛谷 P4568 | 最标准的 \(K\) 次免费机会分层图 |
| [USACO09FEB] Revamping Trails | 洛谷 P2939 | 与飞行路线类似，练手感 |
| 冻结 Freezing | 洛谷 P4822 | 消耗机会使边权减半 |
| 回家的路 | 洛谷 P5471 | 涉及到复杂的节点拆分和多状态跳转 |
坑
空间复杂度： 分层图最容易 MLE (内存超限)。如果原图有 \(V\) 个点 \(E\) 条边，分层后会变成 \((K+1)V\) 个点和 \((2K+1)E\) 条边。建图时数组一定要开够大。
层间连边的方向： 特殊机会通常是“不可逆”的，所以层间边通常是单向的（从第 \(i\) 层指向第 \(i+1\) 层），否则会产生逻辑错误。
多终点问题：
在消耗 \(K\) 次机会的问题中，答案不一定非得用完 \(K\) 次。
- 错误做法： 只输出
dist[target][K]。 - 正确做法： 答案应该是 \(\min_{i=0}^{K} \{dist[target][i]\}\)。或者，在建图时从
(target, i)向(target, i+1)连一条权值为 0 的单向边，这样直接取dist[target][K]即可。
边数预估（重点）：
很多入开了 N * (K+1) 的点数组，却忘了边数组 M 也要相应翻倍。对于 [ABC395E]，总边数是 \(2M + N\)（正向边 + 反向边 + 跨层连接边）。