G. X Aura - 题解

比赛与标签

比赛: 2024-2025 ICPC Asia Jakarta Regional Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred) 标签: graphs, math, shortest paths 难度: *2200

题目大意喵~

主人，我们被传送到了一个叫作 ICPC 山的地方！这座山可以看作是一个 R 行 C 列的网格，每个格子 (r, c) 都有一个特定的高度 H(r,c)。

我们可以在相邻的格子里移动（上、下、左、右），但每次移动都要付出代价（penalty）的说。这个代价的计算方式很特别：如果我们带着一个奇数 X 的光环，从高度为 h1 的格子移动到高度为 h2 的格子，代价就是 (h1 - h2)^X。注意哦，这个代价可能是负数！

现在有 Q 个任务，每个任务都会给我们一个起点 (Rs, Cs) 和一个终点 (Rf, Cf)。我们需要找到从起点到终点的路径，使得总代价最小。

但是，这里有个陷阱！在某些情况下，总代价可以变得无限小（比如通过在一个代价为负的环路里不停地绕圈圈）。这种情况我们称之为 "invalid"（无效）。

我们的任务就是：对于每个询问，要么计算出最小的总代价，要么告诉出题人这是 "INVALID" 的情况。

解题思路大揭秘！

这道题的核心是求最短路径，但这个边权 (h1 - h2)^X 看起来太奇怪了，直接用 Dijkstra 或者 SPFA 可能会很麻烦，甚至会因为负权环而超时。所以，我们需要用更聪明的办法来驯服它，喵~

关键的变形：势能法！

看到这种 f(u) - f(v) 形式的边权，我们应该立刻想到图论中的一个强大工具——势能法（Potential Method），它也是 Johnson 全源最短路径算法的核心思想。

我们来定义每个节点 v 的一个势能 p(v)。然后，我们将原来的边权 c(u, v) 转换成新的边权 c'(u, v) = c(u, v) - p(u) + p(v)。

这样做有什么好处呢？一条从 s 到 f 的路径 s -> v1 -> v2 -> ... -> f，它的新路径长度是： dist'(s, f) = c'(s, v1) + c'(v1, v2) + ...= (c(s, v1) - p(s) + p(v1)) + (c(v1, v2) - p(v1) + p(v2)) + ...= (c(s, v1) + c(v1, v2) + ...) - p(s) + p(f)= dist(s, f) - p(s) + p(f)

于是，我们得到了一个美妙的关系式： dist(s, f) = dist'(s, f) + p(s) - p(f)

只要我们能巧妙地选择 p(v)，让 c'(u, v) 变得非常简单，问题就解决大半啦！

如何选择势能 `p(v)` 呢？

观察代价公式 c(u, v) = (h_u - h_v)^X，一个自然的想法就是让势能和高度的 X 次方有关。我们来试试 p(v) = h_v^X。

代入新边权的公式： c'(u, v) = (h_u - h_v)^X - h_u^X + h_v^X

当 X = 1 时: c'(u, v) = (h_u - h_v) - h_u + h_v = 0 天哪！所有新边权都变成 0 了！这意味着在同一个连通分量里，任意两点间的 dist' 都是 0。所以 dist(s, f) = 0 + p(s) - p(f) = h_s - h_f。问题瞬间解决！
当 X > 1 时: c'(u, v) 不再是 0 了。但是，我们希望从 s 到 f 的路径代价是唯一的，不依赖于具体走的哪条路。这要求在我们的新图里，任何环路的权重和都为 0。

路径无关性与 "INVALID"

路径无关性的充要条件是任意环路权重为0。我们只需要检查最小的环路——2x2 的小方格。考虑一个 2x2 的方格，四个顶点分别为 a, b, c, d。

a -- b
|    |
d -- c

路径 a -> b -> c 和路径 a -> d -> c 的原始代价应该相等，这样才能保证路径无关。 cost(a->b) + cost(b->c) = cost(a->d) + cost(d->c)(h_a - h_b)^X + (h_b - h_c)^X = (h_a - h_d)^X + (h_d - h_c)^X

如果在一个连通分量里，所有的 2x2 小方格都满足这个等式，我们称这个分量是一致的（consistent）。在一致的分量里，任意两点间的路径代价是固定的。

如果某个分量不满足这个条件，那么它就是不一致的（inconsistent）。这意味着存在一个环路，它的总代价不为 0。假设这个环路代价为 W。因为 X 是奇数，所以 (h1 - h2)^X = -(h2 - h1)^X，即 c(u, v) = -c(v, u)。所以，反向走这个环路，代价就是 -W。W 和 -W 中必有一个是负数！这就找到了一个负权环。我们可以在这个环里无限打转，让总代价变得无限小。所以，只要起点和终点所在的分量是不一致的，答案就是 "INVALID"。

最终的解题步骤

好啦，思路已经清晰了，让我们总结一下完整的步骤吧！

预处理:
- 计算 0^X, 1^X, ..., 9^X 的值。
- 计算所有可能的 h_u, h_v 组合对应的 c'(u, v) = (h_u - h_v)^X - h_u^X + h_v^X 的值。
图的分析:
- 用 BFS 或 DFS 遍历整个网格，找出所有的连通分量，并给每个格子打上分量ID。
- 对于 X > 1 的情况，遍历所有 2x2 的小方格，检查它们是否满足路径无关的等式。如果一个分量内有任何一个方格不满足，就将该分量标记为 "inconsistent"。
计算势能距离:
- 对于每一个一致的连通分量，我们从任一节点（比如分量的第一个被发现的节点）作为根节点 root 开始做一次 BFS。
- 计算从 root 到分量内所有其他节点 v 的新路径长度 dist'(root, v)。我们把它记作 potential[v]。递推关系是 potential[v] = potential[u] + c'(u, v)。
- 注意：代码里的 potential 定义稍有不同，potential[v] = potential[u] - c'(u, v)，这只是符号上的区别，最终结果是一样的哦。
回答询问:
- 对于每个询问 (s, f):
  - 首先检查 s 所在的分量是否被标记为 "inconsistent"。如果是，直接输出 "INVALID"。
  - 如果分量是一致的，那么 dist'(s, f) = dist'(root, f) - dist'(root, s) = potential[f] - potential[s]。
  - 代入最终公式：dist(s, f) = dist'(s, f) + p(s) - p(f)
  - dist(s, f) = (potential[f] - potential[s]) + h_s^X - h_f^X。
  - 根据代码的定义：dist'(s, f) = potential[s] - potential[f]，所以 dist(s, f) = (potential[s] - potential[f]) + h_s^X - h_f^X。计算并输出结果就好啦！

这样，我们通过预处理把问题转换成 O(1) 的查询，非常高效！

AC 代码实现喵~

下面就是一份可以通过此题的完整代码啦，我已经加上了详细的注释，希望能帮助主人更好地理解！

cpp

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <utility>

// 使用 std 命名空间，让代码更简洁喵~
using std::cin;
using std::cout;
using std::vector;
using std::string;
using std::queue;
using std::pair;

// 全局变量，方便在各个函数间使用
int R, C, X;
vector<vector<int>> H; // 存储网格的高度
vector<long long> h_pow_X_vals; // 预计算 h^X 的值
vector<vector<long long>> c_prime_vals; // 预计算 c' 的值
vector<vector<int>> comp_id; // 每个格子的连通分量ID
vector<bool> is_inconsistent; // 标记每个分量是否不一致
vector<vector<long long>> potential; // 存储每个格子的势能距离
vector<pair<int, int>> component_roots; // 每个连通分量的根节点
vector<vector<bool>> visited_potential; // 在计算势能时标记是否访问过

// 网格遍历的方向数组 (上, 下, 左, 右)
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

// 自定义 pow 函数，因为 std::pow 对负数处理不符合题目要求
// 题目保证 X 是奇数，所以 (-a)^X = -a^X
long long custom_pow(long long base, int exp) {
    long long res = 1;
    if (base == 0) return 0;
    bool neg = base < 0;
    base = std::abs(base);
    for (int i = 0; i < exp; ++i) {
        res *= base;
    }
    if (neg) {
        return -res;
    }
    return res;
}

// 预处理 h^X 和 c' = (h1-h2)^X - h1^X + h2^X
void precompute() {
    h_pow_X_vals.resize(10);
    for (int i = 0; i <= 9; ++i) {
        h_pow_X_vals[i] = custom_pow(i, X);
    }

    c_prime_vals.assign(10, vector<long long>(10));
    for (int i = 0; i <= 9; ++i) {
        for (int j = 0; j <= 9; ++j) {
            c_prime_vals[i][j] = custom_pow(i - j, X) - h_pow_X_vals[i] + h_pow_X_vals[j];
        }
    }
}

// 用 BFS 找到所有连通分量
void find_components() {
    comp_id.assign(R + 1, vector<int>(C + 1, -1));
    int current_comp_id = 0;
    for (int r = 1; r <= R; ++r) {
        for (int c = 1; c <= C; ++c) {
            if (comp_id[r][c] == -1) {
                component_roots.push_back({r, c}); // 记录每个分量的根
                queue<pair<int, int>> q;
                q.push({r, c});
                comp_id[r][c] = current_comp_id;
                while (!q.empty()) {
                    pair<int, int> curr = q.front();
                    q.pop();
                    for (int i = 0; i < 4; ++i) {
                        int nr = curr.first + dr[i];
                        int nc = curr.second + dc[i];
                        if (nr >= 1 && nr <= R && nc >= 1 && nc <= C && comp_id[nr][nc] == -1) {
                            comp_id[nr][nc] = current_comp_id;
                            q.push({nr, nc});
                        }
                    }
                }
                current_comp_id++;
            }
        }
    }
    is_inconsistent.assign(current_comp_id, false);
}

// 检查每个分量是否一致
void check_consistency() {
    if (X == 1) return; // X=1时，所有分量都是一致的，喵~
    // 遍历所有 2x2 的小方格
    for (int r = 1; r < R; ++r) {
        for (int c = 1; c < C; ++c) {
            int id = comp_id[r][c];
            if (is_inconsistent[id]) continue; // 如果分量已经不一致，就跳过

            // 检查 (r,c), (r,c+1), (r+1,c+1), (r+1,c) 是否在同一分量
            if (id == comp_id[r + 1][c] && id == comp_id[r][c + 1] && id == comp_id[r + 1][c + 1]) {
                int h_a = H[r][c];
                int h_b = H[r][c + 1];
                int h_c = H[r + 1][c + 1];
                int h_d = H[r + 1][c];

                // 检查路径无关性条件
                long long lhs = custom_pow(h_a - h_b, X) + custom_pow(h_b - h_c, X);
                long long rhs = custom_pow(h_a - h_d, X) + custom_pow(h_d - h_c, X);

                if (lhs != rhs) {
                    is_inconsistent[id] = true; // 标记为不一致
                }
            }
        }
    }
}

// 为所有一致分量中的格子计算势能距离
void compute_potentials() {
    potential.assign(R + 1, vector<long long>(C + 1, 0));
    visited_potential.assign(R + 1, vector<bool>(C + 1, false));

    for (size_t i = 0; i < component_roots.size(); ++i) {
        if (X > 1 && is_inconsistent[i]) continue; // 跳过不一致的分量

        pair<int, int> root = component_roots[i];
        queue<pair<int, int>> q;

        q.push(root);
        potential[root.first][root.second] = 0; // 根节点的势能距离为0
        visited_potential[root.first][root.second] = true;

        // BFS 计算分量内所有节点的势能距离
        while (!q.empty()) {
            pair<int, int> curr = q.front();
            q.pop();
            int ur = curr.first;
            int uc = curr.second;

            for (int j = 0; j < 4; ++j) {
                int vr = ur + dr[j];
                int vc = uc + dc[j];

                if (vr >= 1 && vr <= R && vc >= 1 && vc <= C && !visited_potential[vr][vc] && comp_id[vr][vc] == (int)i) {
                    visited_potential[vr][vc] = true;
                    // potential[v] = potential[u] - c'(u,v)
                    potential[vr][vc] = potential[ur][uc] - c_prime_vals[H[ur][uc]][H[vr][vc]];
                    q.push({vr, vc});
                }
            }
        }
    }
}

int main() {
    // 加速输入输出，对付大数据量必备！
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> R >> C >> X;

    H.assign(R + 1, vector<int>(C + 1));
    for (int i = 1; i <= R; ++i) {
        string row;
        cin >> row;
        for (int j = 1; j <= C; ++j) {
            H[i][j] = row[j - 1] - '0';
        }
    }

    // 按照我们的解题步骤来执行
    precompute();
    find_components();
    check_consistency();
    compute_potentials();

    int Q;
    cin >> Q;
    while (Q--) {
        int rs, cs, rf, cf;
        cin >> rs >> cs >> rf >> cf;

        int cid = comp_id[rs][cs];
        // 如果起点所在分量不一致（且X>1），就是INVALID
        if (X > 1 && is_inconsistent[cid]) {
            cout << "INVALID\n";
        } else {
            // dist'(s,f) = potential[s] - potential[f]
            long long dist_prime = potential[rs][cs] - potential[rf][cf];
            // dist(s,f) = dist'(s,f) + p(s) - p(f)
            long long ans = dist_prime + h_pow_X_vals[H[rs][cs]] - h_pow_X_vals[H[rf][cf]];
            cout << ans << "\n";
        }
    }

    return 0;
}

复杂度分析

时间复杂度: O(R * C + Q) 的说。
- 预处理、找连通分量、检查一致性、计算势能，这些步骤都只需要遍历一遍网格，所以是 O(R * C)。
- 之后回答每个询问只需要 O(1) 的时间进行查表和计算。
- 总时间就是 O(R * C + Q)，非常快喵！
空间复杂度: O(R * C) 的说。
- 我们需要存储地图 H、分量ID comp_id、势能 potential 等等，这些都需要和网格大小成正比的空间，所以是 O(R * C)。

知识点与总结

这道题真是一次愉快的思维探险呢！它教会了我们：

势能法: 面对形式奇特的边权，可以尝试引入势能 p(v)，将边权 c(u,v) 转换为 c(u,v) - p(u) + p(v)，从而简化问题。这是解决一类最短路问题的强大技巧。
路径无关性: 当图中任意环路权重为0时，两点间的路径积分（或路径代价）就与具体路径无关。在网格图中，这通常可以通过检查最小的 2x2 环路来验证。
负权环与INVALID: “可以获得无限小代价”的本质就是图中存在负权环路。通过我们的分析，一个“不一致”的分量就等价于存在负权环。
分而治之: 先将图分解成连通分量，再对每个分量进行独立分析（判断一致性、计算势能），是一种清晰且高效的解题策略。

希望这次的讲解能帮到主人哦！如果还有其他问题，随时可以再来找我玩，喵~ 祝主人刷题愉快，场场 AK！(>^ω^<)

G. X Aura - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路大揭秘！ ​

关键的变形：势能法！ ​

如何选择势能 p(v) 呢？ ​

路径无关性与 "INVALID" ​

最终的解题步骤 ​

AC 代码实现喵~ ​

复杂度分析 ​

知识点与总结 ​