Skip to content

分层图

本文主要介绍分层图这一建图技巧。

分层图这个建图技巧最常见的一个模型是： 我们要在一个图上进行若干次决策，而对于每一次具体的决策， 其都不会改变图的结构，只会改变状态与代价。

这么说可能有点抽象，我们来看一道经典例题：

「JLOI2011」飞行路线

题意简述：

给定一个有 \(n\) 个点 \(m\) 条边的带边权无向图， 从中选择 \(k\) 条边，使他们的边权变成 \(0\)， 求给定两点之间的最短路。

保证 \(n \leq 10^4,m \leq 5 \times 10^4,k \leq 10\)

考虑暴力做法， 枚举从 \(m\) 条边里选出哪 \(k\) 条变成 \(0\)，一共有 \(\displaystyle \binom{m}{k}\) 种情况， 每种情况跑一次 \(\text{Dijkstra}\)，复杂度大致是 \(\displaystyle O \left( \binom{m}{k} m \log m \right)\)，显然无法接受。

暴力做法的瓶颈显然在于我们枚举 \(k\) 条边的开销，我们接下来考虑这个。

我们先考虑一下最简单的情况，就是 \(k=0\) 的情况，这个很好办，直接跑最短路就行了。 假设存在这样一个图：

img.png

我们对着这个图去考虑 \(k=1\) 的情况，这个图非常简单， 我们一眼就能够看出直接选择 \(2 \to 3\) 这条边就可以了。 但是显然我们需要找一些更通用的方法，我们考虑再建一个一模一样的图：

img_1.png

我们叫上面这个图第零层，叫下面这个图第一层。 问题在于我们如何解决「边的代价为 \(0\)」这个事情。 我们考虑在第零层和第一层之间连有向边，如下图所示：

img_2.png

相信聪明的你此时已经看出来了，我们只要钦定这些红色的「跨层」的边代价为 \(0\)， 之后直接跑最短路就可以了，最后从第零层的 \(1\) 到达第一层 \(4\) 的最短路， 就是我们要找的答案。

于是我们可以给「层」加上更加明确的意义， 在这个题中，我们所谓的第 \(i\) 层，本质上就是在使用 \(i-1\) 条「免费」的边之后， 我们能够到达所有点的最短距离。

例如第 \(1\) 层，我们使用了 \(0\) 条「免费」边； 而在第 \(2\) 层，我们使用了 \(1\) 条「免费」边， 以此类推，我们把这个东西拓展到 \(k+1\) 层，之后去跑最短路， 就可以解决「\(k\) 条免费边」的问题了。

需要注意的细节

大概的思想理解了，不过接下来我们有一些细节问题需要思考。

首先，我们如何实现开 \(k\) 层图并且让层与层之间产生联系这个问题， 我们真的需要去开 \(k+1\) 个邻接表吗（别忘了原图也需要一个邻接表）？

其实不用，假设我们存在一个 \(n\) 个点的图， 那么我们对于第零层的点分别标 \(1\) 到 \(n\)， 然后对于第一层的图，我们的标号从 \(n+1\) 开始一直到 \(2n\)。 这样一来，我们直接维护一个 \((k+1) \times n\) 的邻接表， 当我们想要访问第 \(i\) 层的 \(j\) 号点的时候， 我们就可以直接用 \(i \times n + j\) 来访问（这里我们假设层的编号从 \(0\) 开始）。

当我们想要连一条第 \(k\) 层 \(i\) 点，到第 \(k+1\) 层 \(j\) 点的时候， 我们可以直接从邻接表上 \(k \times n + i\) 连一条到 \((k+1) \times n + j\) 的边。

其次还有另一个问题，当我们建好了一个 \(k+1\) 层的图， 并且跑完最短路之后，答案是否是从第零层的起点到最后一层的终点的距离？

答案是不一定，这个东西需要自行根据题目特性来决定。 有些时候你需要综合考虑每一层到达终点的答案来决定， 比如题目要求的到底是「最多」还是「恰好」。

我们拿这个例题来举例子，这个题目里要求的是「最多」\(k\) 条边， 也就是说我们并不一定要把 \(k\) 次机会用完， 如果我们硬要把 \(k\) 次机会用完， 反而可能产生更劣的答案。 例如当 \(n=2\) 且 \(k=2\) 时，就会出现我所说的情况， 这里我们不画图讲解了，留给读者自行思考。

通常来说，在很多「最多使用 \(k\) 次」的题目里， 最优解都很有可能落在中间层而不是最后一层。

当然，如果题目的限制改成「必须把 \(k\) 次机会全用掉」。 那么我们就只能在最后一层寻找答案了。

参考代码 
typedef pair<int,int> PII;

void IHaveNoLimitation() {
    int n, m, k;
    cin >> n >> m >> k;
    int s, t;
    cin >> s >> t;
    vector<vector<PII>> adj((k + 1) * n + 5);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        for (int j = 1; j <= k; ++j) {
            adj[(j - 1) * n + u].push_back({j * n + v, 0});
            adj[(j - 1) * n + v].push_back({j * n + u, 0});
            adj[j * n + u].push_back({j * n + v, w});
            adj[j * n + v].push_back({j * n + u, w});
        }
    }
    vector<int> dis((k + 1) * n + 5,INT_MAX), vis((k + 1) * n + 5);
    auto dijkstra = [&](int s) {
        dis[s] = 0;
        priority_queue<PII, vector<PII>, greater<PII>> pq;
        pq.push({0, s});
        while (!pq.empty()) {
            auto [w, cur] = pq.top();
            pq.pop();
            if (vis[cur]) continue;
            vis[cur] = 1;
            for (auto &nxt: adj[cur]) {
                auto &[to, val] = nxt;
                if (dis[to] > dis[cur] + val) {
                    dis[to] = dis[cur] + val;
                    pq.push({dis[to], to});
                }
            }
        }
    };
    dijkstra(s);
    int ans = INT_MAX;
    for (int i = 0; i <= k ; i++) {
        ans = min(ans,dis[i * n + t]);
    }
    cout << ans << endl;
}

进一步探讨

接下来我们来更加深入探索一下分层图的本质。

我们可以这样理解分层图的本质： 分层图的本质就是在原图的点上，附加上一个额外的状态。 之后我们在 (点，状态) 的图上，跑最短路或者进行其他操作。

在传统的最短路问题上，我们通常关注的是「我在某个点」的状态。 而在分层图问题中，我们关心的是「我在某个点的同时，用了几次机会/目前是第几步」的状态。 分层图的思想就是我们按照不同的状态，针对每一个状态都单开一个和原图等规模的图。 之后把不同状态下的图进行连接。

如果我们采用更加形式化的说法， 我们可以把分层图的点集看成是原图点集 \(V\) 和一个「状态集合」\(H\) 的笛卡尔积：\(V^{\prime} = V \times H\)。 其中的每个点都形如 \((v,h)\)，表示在原图的点 \(v\) 上，我们对其附加了一个状态 \(h\)。

之后我们就可以在这个新的点集 \(V^{\prime}\) 上，按照题目给出的规则进行状态之间的连边。

分层图技巧通常应用于一些，刻画了特殊规则的图论问题上。

最常见的一类是「最多/恰好使用 \(k\) 次操作」， 这是最常见的一类题目。我们可以执执行最多/恰好 \(k\) 次操作， 每次操作把若干条边的边权变成 \(0\) /每次操作把若干条边的边权减半/可以穿过特殊边至多 \(k\) 次。

这类题目的共同特征是，这个特殊操作的效果，和你之前在哪些位置用过无关， 只和「你已经使用了多少次」相关。 也就是说，我们只需要记录「已用次数 \(x\)」，就足够我们去刻画后续的行为。 于是我们就可以非常自然地开 \(k+1\) 层图， 第 \(i\) 层表示已经用了 \(i\) 次机会。

注意事项

在使用分层图之前我们需要注意一些事情。

首先我们一定要关注状态空间的大小，拿我们前文的题目去举例子的话， 假设这个题的 \(k\) 达到了 \(10^5\)，那我们实际上是没办法非常愉快地维护 \(10^5\) 个和原图规模一样的图的。 或者你想要去记录「我们具体用了哪些边」，这种事情也是做不到的，因为状态数会呈指数级增长。

第二个是，未来的转移是否和之前的转移相关。 如果问题的转移不依赖于「操作剩余次数」，而是依赖于我们之前在哪里使用过或者走过哪些点。 那这种东西除非数据规模很小，否则是无法将其压缩成一个足够小的状态， 来让我们进行分层图的操作的。

拓展

其实某些题目的思想是，要我们先建立分层图， 之后把状态写成 (层，点) 的 \(\text{DP}\)：\(dp[layer][cur]\)。

如果我们建出来的图是一个 \(\text{DAG}\)， 那么这个 \(\text{DP}\) 就很自然了。

相对的，如果建出来的图不是一个 \(\text{DAG}\)， 那你这个时候再去 \(\text{DP}\) 就稍显诡异了， 但是在这个图上跑最短路依然是一个非常好的选择。

日志

本页面创建于 2025/12/01 17:19