P7297(Telephone G)题解

· · 题解

本题解旨在更清晰地讲解分层图算法在此题的应用。

图1

4 3
1 2 3 2
101
011
110

对于这一组数据，如果 \operatorname{O}(n^2) 暴力处理，显然会得到这样的图。

如何对其进行优化？

观察到 k 较小，这种点的种类较少的题，分层图可以作为一个思考方向。

所谓分层，层与层之间维持有限制条件的联系，而层内部看作一个整体。

观察式子 |i - j| ，不难发现它的实质是一条边权为1的“链”上点 i 和点 j 之间的距离。因此，可以在层内部以 (i, i + 1) 的方式连边。这里连无向边，因为一层是一个整体， (i,j) 和 (j, i) 的连通性、权值相同。

把一层看作一个整体后，通过层与层之间不同点的关系维持题目当中 S 的限制条件。

（第 k 层的点 u 记作 \operatorname{get}(u, k) ）

考虑第 1 ~ k 层对于第 0 层的意义。第 b[u] 层的点 u 完全“继承”第 0 层的点 u 。 我们对第0层的点 u 和 \operatorname{get}(u, b[u]) 连一条边权为0的有向边，把 b[u] 层的所有点“固定”到点 u 上。

然后，对于满足 S_{k, b[u]} = 1 的所有组合，由 \operatorname{get}(u, k) 向第 0 层点 u 连接有向边。

如果经过被“固定”到点 u 的若干点又能从点 \operatorname{get}(v, b[u]) 回到第 0 层点 v ，那么就等同于建立了有向边 (u, v) 。根据层内连边的规则，不难发现在第 b[u] 层经过的边权之和即为 |u - v| 。

这样，我们便巧妙地转化了 S 所给出的限制条件。

可以借助图2理解。

图2

代码实现上 ，仍然将 n 作为终点，所有非第 0 层点都作为中间“过渡”点。

设置 \operatorname{get}(u, k) = u + n \times k 作为由第 0 层的 u 跳转到第 k 层对应点的标志。

P.S. 当一个图只含有边权为 0, 1 的两种边的时候，可以用双端队列BFS进一步优化掉Dijkstra的一个 \operatorname{log} （不过不用也没什么关系）

Code

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define mp make_pair
const int N = 5e4 + 10, M = 52;
int n, k, b[N];
char s[M][M];
vector<PII> e[N * M];
int dist[N * M];
void Add(int x, int y, int w = 0, int f = 0) { e[x].push_back(mp(y, w)); if(f) e[y].push_back(mp(x, w)); }
#define get_l(x, t) ((x) + (t) * n) // 第t层点x的映射
void build() {
    // 1. 1至n层内部连边
    for(int i = 1; i <= k; i ++ )
        for(int j = 1; j <= n - 1; j ++ )
            Add(get_l(j, i), get_l(j + 1, i), 1, 1);
    // 2. 由第0层向其它层等效加边
    for(int i = 1; i <= n; i ++ ) Add(i, get_l(i, b[i]));
    // 3. 由其它层向第0层等效加边
    for(int i = 1; i <= k; i ++ )
        for(int j = 1; j <= n; j ++ )
            if(s[i][b[j]] == '1') Add(get_l(j, i), j);
}
void work() {
    #ifdef debug
    for(int i = 1; i <= get_l(n, k); i ++ ) {
        for_each(e[i].begin(), e[i].end(), [](PII x) -> void { cout << x.first << " "; });
        cout << endl;
    }
    #endif
    memset(dist, 0x3f, sizeof dist);
    deque<int> Q;
    Q.push_back(1); dist[1] = 0;
    while(!Q.empty()) {
        int t = Q.front(); Q.pop_front();
        for(unsigned i = 0; i < e[t].size(); i ++ ) {
            int u = e[t][i].first, w = e[t][i].second;
            if(dist[u] > dist[t] + w) {
                dist[u] = dist[t] + w;
                if(w) Q.push_back(u);
                else Q.push_front(u);
            }
        }
    }
    printf("%d\n", dist[n] > 1e9 ? -1 : dist[n]);
}
int main() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i ++ ) scanf("%d", b + i);
    for(int i = 1; i <= k; i ++ )
        scanf("%s", s[i] + 1); // 下标从1开始
    build();
    work();
    return 0;
}