一、分層圖的核心思想

分層圖是一種將圖的不同狀態拆分為多個“層”的建模方法，每層對應一種特定狀態。通過這種方式，可以將復雜的狀態轉移問題轉化為多層圖中的最短路徑問題。

核心特點：

• 層內邊：表示普通操作（如正常行走）。
• 層間邊：表示狀態轉移（如使用一次特殊能力、改變狀態等）。
• 狀態壓縮：通常通過 j * n + u 的方式編號節點（j 表示層數，u 是原圖節點）。

---

二、分層圖的構建方法

1. 物理構圖

   • 定義：直接將圖復制為 k 層，每層節點數為 n。
   • 層內邊：與原圖相同，邊權不變。
   • 層間邊：按狀態轉移規則添加（如使用一次特殊能力）。
   • 適用場景：k 較小（如 k ≤ 10）。
   • 缺點：空間消耗大（總節點數為 k * n）。

2. DP 構圖

   • 定義：通過動態規劃模擬狀態轉移，無需顯式構建多層圖。
   • 狀態表示：使用二維數組 dis[u][j] 表示在節點 u、狀態 j 下的最短距離。
   • 適用場景：狀態維度較大的問題（如時間、鑰匙狀態等）。
   • 優點：節省空間，適合高維狀態。

---

三、分層圖的典型應用場景

1. 有限次決策

   • 例題：允許最多使用 k 次特殊能力（如免費邊、升級等）。
   • 建模：構建 k+1 層圖，層間邊表示使用能力。

2. 狀態依賴

   • 例題：鑰匙狀態、時間余數、奇偶性等。
   • 建模：根據狀態分層（如鑰匙狀態用二進制編碼）。

3. 多維狀態轉移

   • 例題：同時考慮時間、資源、權限等狀態。
   • 建模：每個維度對應一層，組合成多維分層圖。

---

四、分層圖的詳細例題與實現

例題 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});}}}
}

---

六、分層圖的優化技巧

1. 空間優化

   • 物理構圖：總節點數為 k * n，邊數為 k * m + ...。
   • DP 構圖：狀態數為 n * 2^p（p 為鑰匙種類數）。

2. 時間優化

   • 使用 01BFS（邊權為 0 或 1 時）。
   • 使用 優先隊列優化的 Dijkstra（邊權任意值）。

3. 狀態壓縮

   • 對于鑰匙狀態，用二進制位壓縮。
   • 對于時間余數，用 t % k 表示。

---

七、分層圖的適用場景總結

場景類型	示例問題	分層依據	構圖方式
有限次決策	免費邊、升級	使用次數	物理構圖
狀態依賴	鑰匙、時間余數	鑰匙狀態、余數	DP 構圖
多維狀態轉移	資源、權限	組合狀態	DP 構圖

---

八、分層圖的常見錯誤與調試

1. 節點編號錯誤：確保 u + j * n 正確映射層和節點。
2. 層間邊方向錯誤：層間邊應單向（如從 j 層到 j+1 層）。
3. 初始化錯誤：dis 數組未初始化為最大值。
4. 優先隊列優先級錯誤：使用 greater<> 保證最小堆。