浅谈分层图最短路
什么是分层图？
所谓分层图，即通过构建一张新图使得一张图有多个维度。一个典型的例子是使一张图复制出一份或多份，并在复制出的不同的层之间根据要求连接某些点。
一个典型的应用就是在不同路径上有 kkk 个决策 p1,p2,p3p_1,p_2,p_3p1,p2,p3 ，那么对于每个决策 pip_ipi ，我们构建一层新的图使得边 E(u,v)E(u,v)E(u,v) 可以用来表示决策 pip_ipi 。后续的操作经常使用最短路/最长路相关算法求解。
例题
P4568 [JLOI2011] 飞行路线
题目概述
给定一个包含 nnn 个节点和 mmm 条边的带权无向图 GGG （节点由 0∼n−10 \sim n - 10∼n−1 编号）和 kkk 次决策（0≤k≤100 \leq k \leq 100≤k≤10），对于每个决策 DiD_iDi ，可以以 000 为边权通过任意一条边一次。求从节点 sss 到 ttt 的最小花费。
分析
容易发现在不考虑进行决策的情况下（即 k=0k=0k=0 时），题目转化为求无向图上的最短路径。显然可以通过 Dijkstra 等算法在 O(mlogm)O(m \log m)O(mlogm) 时间内解决。
考虑进行决策。对于每一条边，我们都可以有选择按照原有边权走或者按边权为 000 走两种选择。显然后者只能选择最多 kkk 次（不一定要全选完 kkk 次）。那么，我们不妨对于每条边 E(u,v,w)E(u,v,w)E(u,v,w) 增设一个决策边 E′(u,v,0)E'(u,v,0)E′(u,v,0) ，即选择走边 E′E'E′ 意味在边 EEE 上进行一次决策。
接下来我们需要考虑限定 kkk 次决策。容易发现，在上图中，我们在下层新建了 nnn 个节点 V0′∼V1′V_0' \sim V_1'V0′∼V1′ ，并将决策边的终点设在了第二层对应点上。这样，对于每一次决策，我们都可以保证单向性（上层的点只能到达下层）。同时，因为每一层的节点之间都有来自原始图的连边，所以不会影响正常边的统计。
显然，对于 kkk 次决策，我们只需要建立 kkk 层上述的图即可。
代码
#include
using namespace std;
const int N = 2e5 + 10;
int n, m, K, s, t;
struct Edge {
int v, w;
};
vector
int dis[N], vis[N];
void addEdge(int u, int v, int w) {
G[u].push_back(Edge{v, w});
}
void dijkstra(int u) {
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
struct Node {
int dis, u;
bool operator>(const Node& a) const {
return dis > a.dis;
}
};
priority_queue
q.push(Node{0, u});
dis[u] = 0;
while (!q.empty()) {
Node curr = q.top();
q.pop();
int u = curr.u;
if (vis[u]) continue;
vis[u] = 1;
for (auto edge : G[u]) {
int v = edge.v, w = edge.w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push(Node{dis[v], v});
}
}
}
}
int main() {
for (int i = 0; i < N; i++) G[i].clear();
scanf("%d%d%d", &n, &m, &K);
scanf("%d%d", &s, &t);
s++, t++;
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
u++, v++;
addEdge(u, v, w);
addEdge(v, u, w);
for (int i = 1; i <= K; i++) {
int uu = i * n + u, vv = i * n + v;
addEdge(uu, vv, w);
addEdge(vv, uu, w);
addEdge((i - 1) * n + u, vv, 0);
addEdge((i - 1) * n + v, uu, 0);
}
}
dijkstra(s);
int ans = 0x3f3f3f3f;
for (int i = 0; i <= K; i++) {
ans = min(ans, dis[i * n + t]);
}
printf("%d\n", ans);
return 0;
}
需要注意的是，在统计答案时我们需要在 kkk 层中取最小值，因为不一定需要 kkk 次决策才能到达终点。
P3119 [USACO15JAN] Grass Cownoisseur G
题目概述
给定一个 nnn 个点 mmm 条边的有向图 GGG 和 111 次决策，求从 111 号节点返回到 111 号节点的最长路。
定义一次决策为将任意一条边 E(u,v)E(u,v)E(u,v) 变为 E′(v,u)E'(v, u)E′(v,u) 。
分析
考虑建图。显然可以将决策转化为分层图求解。
对于原图 GGG ，我们新建一个图 G′G'G′ 使得 G′=GG'=GG′=G 。然后，我们对于 E(u,v)∈GE(u,v) \in GE(u,v)∈G ，E′(u′,v′)∈G′E'(u',v') \in G'E′(u′,v′)∈G′ 间建立有向边 E′′(v,u′)E''(v, u')E′′(v,u′) ，即对于原图和复制图中的每个点之间建立反向边。
然后可以考虑求最长路。显然上述做法建出来的图无法保证是 DAG ，故先进行 Tarjan 缩点后重新建带权图，最后使用拓扑排序求最长路。
代码
#include
using namespace std;
const int N = 2e5 + 10;
int n, m;
int dfn[N], low[N], color[N], sccCnt = 0, idx = 0, vis[N];
set
stack
int dis[N], inDegree[N];
class Graph {
private:
vector
public:
int inDegree[N];
void addEdge(int u, int v) {
G[u].push_back(v);
inDegree[v]++;
}
vector
return G[x];
}
} G, G2;
void tarjan(int u) {
dfn[u] = low[u] = ++idx;
vis[u] = 1;
s.push(u);
for (auto v : G[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (vis[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
sccCnt++;
while (!s.empty()) {
int x = s.top();
s.pop();
scc[sccCnt].insert(x);
color[x] = sccCnt;
vis[x] = 0;
if (u == x) break;
}
}
}
void toposort(int s) {
queue
for (int i = 1; i <= sccCnt; i++) {
if (G2.inDegree[i] == 0) q.push(i);
}
dis[s] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto v : G2[u]) {
G2.inDegree[v]--;
if (G2.inDegree[v] == 0) {
q.push(v);
}
if (dis[u] >= 0) dis[v] = max(dis[v], dis[u] + (int)scc[v].size());
}
}
}
int main() {
memset(dis, -0x3f, sizeof(dis));
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
G.addEdge(u, v);
G.addEdge(v, u + n);
G.addEdge(u + n, v + n);
}
for (int i = 1; i <= 2 * n; i++) {
if (!dfn[i]) tarjan(i);
}
for (int u = 1; u <= 2 * n; u++) {
for (auto v : G[u]) {
if (color[u] == color[v]) continue;
G2.addEdge(color[u], color[v]);
}
}
toposort(color[1]);
printf("%d\n", max(dis[color[1]], dis[color[1 + n]]));
return 0;
}
总结
分层图是一种实用的建图思想，可以解决多种图上决策问题。实际使用中需要注意层与层之间的联系，必要时可结合 Tarjan 缩点后处理。