“分层图”思想
前置芝士：最短路算法
所谓分层图，即把一整个完整的图，分为若干层，每层对应着原图中的某种状态。
分层图每一层大致有如下特点：
- 每一层极为相似甚至相同，以至于通常只需要在逻辑上划分出层次即可；
- 层层之间有拓扑序；
- 每一层都对应原图中的某一种状态。
而分层图的边通常有两种情况：
- 一条边 \((u, v, w)\)，其中 \(u, v\) 在同一层，那么不做改变，连接一条 \(u\) 到 \(v\)，权重为 \(w\) 的边；
- 一条边 \((u, v, w)\)，其中 \(u, v\) 不在同一层，那么做改变，连接一条 \(u\) 到 \(v\)，权重为 \(w'\) 的边，\(w'\) 的具体值视题目要求而定。
注意： 由于有很多层，分层图的数据范围通常和状压一样，有很明显的特征，如果数据很大那么分层图可能不适用。
例题1
题目描述
约翰一共有 \(N\) 个牧场.由 \(M\) 条布满尘埃的小径连接。小径可以双向通行。每天早上约翰从牧场 \(1\) 出发到牧场 \(N\) 去给奶牛检查身体。
通过每条小径都需要消耗一定的时间。约翰打算升级其中 \(K\) 条小径，使之成为高速公路。在高速公路上的通行几乎是瞬间完成的，所以高速公路的通行时间为 \(0\)。
请帮助约翰决定对哪些小径进行升级，使他每天从 \(1\) 号牧场到第 \(N\) 号牧场所花的时间最短。
思路
如果直接枚举所有可能的高速公路情况，需要枚举 \(C_m^k\) 时间复杂度是 \(O(m^k)\)，绝对不行。
可以发现，如果按升级的高速公路数量为依据，对原图所有状态进行划分，将其分为：
-
\(0\) 层，不建高速公路
-
\(1\) 层，建 \(1\) 条高速公路
-
\(2\) 层，建 \(2\) 条高速公路
-
......
-
\(k\) 层，建 \(k\) 条高速公路
按照连边的思想，应该这么连：
- 一条边 \((u, v, w)\)，其中 \(u, v\) 在同一层，那么不做改变，连接一条 \(u\) 到 \(v\)，权重为 \(w\) 的边，表示布满尘埃的小径；
- 一条边 \((u, v, w)\)，其中 \(u\) 在 \(i\) 层，\(v\) 在 \(i + 1\) 层（规定不能一次性修建两条或删除高速公路），那么做改变，连接一条 \(u\) 到 \(v\)，权重为 \(w'\) 的边，\(w'\) 的具体值在此题中应为 \(0\)，相当于原本要花费 \(w\) ，但是现在免费了，同时状态改变，表示高速公路。
而最后的答案即为每一层，也就是修建任意条高速公路中 \(n\) 号点的最短路中的最小值
对样例进行建图：
由于 \(k == 1\) 所以只有两层，分别对应
不建高速公路和建一条高速公路。
- 如果不修建高速公路，路径是 \(1\rightarrow 2 \rightarrow 4\)，答案是 \(10 + 10 = 20\)；
- 如果修建一条高速公路，路径是 \(1\rightarrow 3 \rightarrow 4'\)，答案是 \(1 + \bcancel{100}0 = 1\)
正确答案是：\(\min{(20, 1)} = 1\)
Code
// Problem: P2939 [USACO09FEB]Revamping Trails G
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2939
// Memory Limit: 125 MB
// Time Limit: 2000 ms
// Author: Moyou
// Copyright (c) 2022 Moyou All rights reserved.
// Date: 2022-12-09 22:28:27
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <iostream>
#include <queue>
#include <stack>
#define int long long
#define x first
#define y second
#define INF 0x7f7f7f7f7f7f7f7f
#define speedup (ios::sync_with_stdio(0), cin.tie(0), cout.tie(0))
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e4 + 10, M = N * 21 + 10, E = 5e4 * 2 + 5e4 * 4 * 20 + 10;
int h[M], e[E], ne[E], w[E], idx;
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int dist[M];
bool st[M];
void dijkstra(int s)
{
memset(dist, 0x7f7f, sizeof dist);
dist[s] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, s});
while (heap.size())
{
auto t = heap.top().y;
heap.pop();
if (st[t])
continue;
st[t] = 1;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
heap.push({dist[j], j});
}
}
}
}
signed main()
{
memset(h, -1, sizeof h);
int n, m, k;
cin >> n >> m >> k;
for (int i = 1; i <= m; i++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
for (int j = 1; j <= k; j++)
{
add(n * j + a, n * j + b, c), add(n * j + b, n * j + a, c);
add(n * (j - 1) + a, n * j + b, 0), add(n * (j - 1) + b, n * j + a, 0);
}
}
dijkstra(1);
int ans = 1e18;
for (int i = 0; i <= k; i++)
{
ans = min(ans, dist[n * i + n]);
}
cout << ans << endl;
return 0;
}
例题2
前置芝士：\(\text{01BFS}\)
一个网格图，其中格子之间有墙或是门，门需要拿到对应的钥匙才可以开启，钥匙分布在网格图之中，问从 \((1,1)\) 走到 \((n, m)\) 的最短距离。
思路
可以发现，这题的钥匙种类 \(P(P\leq 10)\)，因此可以以这个为依据分层。
- \(0\) 层，不拿钥匙
- \(1\) 层，拿 \(1\) 号钥匙
- \(2\) 层，拿 \(2\) 号钥匙
- \(3\) 层，拿 \(1, 2\) 号钥匙
- ......
- \(p\) 层，拿 \(p\) 号钥匙（其中 \(p\) 表示的是二进制下的钥匙状态）。
同时发现一个性质，如果当前格子有钥匙那么就一定会拿，这样可能不赚，但是绝对不亏，所以如果当前格子有钥匙，就向下一层连一条边权为 \(0\) 的边，再加上原本的图，分层图就建好了。
由于边权只有 \(0，1\) 我们可以采用 \(\text{01BFS}\) 实现算法。
我的代码采用逻辑建边。
Code
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 11, NN = (N * N), M = 410, P = (1 << 10) + 10;
int n, m, p, s;
int k;
map<PII, bool> ha; // 是否是墙
int h[NN], e[M], ne[M], w[M], idx;
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int key[NN]; // 表示i点里钥匙的状态
int get(int x, int y) // 二维的点映射到一维上
{
return (x - 1) * m + y;
}
void init()
{
memset(h, -1, sizeof h);
cin >> n >> m >> p >> k;
for(int i = 1; i <= k; i ++)
{
int a, b, aa, bb, c;
cin >> a >> b >> aa >> bb >> c;
int x = get(a, b), y = get(aa, bb);
ha[{x, y}] = ha[{y, x}] = 1;
if(c)
add(x, y, c), add(y, x, c); // 这里c表示的是边的类型
}
cin >> s;
for(int i = 1; i <= s; i ++)
{
int a, b, c;
cin >> a >> b >> c;
key[get(a, b)] |= 1 << c;
}
}
void build() // 建立普通格子间的边
{
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
for(int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
for(int t = 0; t < 4; t ++)
{
int x = i + dx[t], y = j + dy[t];
if(x > n || y > m || x < 1 || y < 1 || ha[{get(i, j), get(x, y)}]) continue;
add(get(i, j), get(x, y), 0);
}
}
int dist[NN][P];
bool st[NN][P];
int bfs(int sta)
{
memset(dist, 0x3f, sizeof dist);
dist[sta][0] = 0;
deque<PII> q;
q.push_front({sta, 0});
while(q.size())
{
auto t = q.front();
q.pop_front();
if(st[t.x][t.y]) continue;
st[t.x][t.y] = 1;
if(t.x == get(n, m)) return dist[t.x][t.y];
if(key[t.x]) // 有钥匙拿钥匙
{
int state = t.y | key[t.x];
if(dist[t.x][state] > dist[t.x][t.y] + 0)
{
dist[t.x][state] = dist[t.x][t.y];
q.push_front({t.x, state});
}
}
for(int i = h[t.x]; ~i; i = ne[i])
{
int j = e[i];
if(w[i] && !(t.y >> w[i] & 1)) continue;
if(dist[j][t.y] > dist[t.x][t.y] + 1)
{
dist[j][t.y] = dist[t.x][t.y] + 1;
q.push_back({j, t.y});
}
}
}
return -1;
}
int main()
{
init();
build();
cout << bfs(1) << endl;
return 0;
}