版本3代码

在之前的讲解中我提到了**并查集（Kruskal 思想）**是解决此类“最小化最大边权”问题的进阶技巧，但未给出完整代码。

在 NOI 竞赛中，并查集方案往往比 Dijkstra 更好写，且在某些特定数据下表现更稳健。下面是完整的版本三代码及深度解析。

版本三：并查集 + Kruskal 算法 (进阶方案)

思路启发（图图形化思考过程）：

1. 网格转边：想象每一个格子是一个“零件”，相邻格子之间有一条“连向彼此的传送带”，传送带的“造价”就是高度差。
2. 排序：我们将所有“传送带”按造价从低到高排好序。
3. 修路：我们从造价最低的传送带开始修建。每修一条，就用并查集把两个零件连在一起。
4. 目标：每修完一条路，就检查一下“左上角”和“右下角”是否已经连通了。
5. 结论：当它们第一次连通时，当前修建的这条路的造价，就是我们要找的“最小体力消耗”。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

// 边的结构体
struct Edge {
    int u, v, w;
    // 按权值（高度差）从小到大排序
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

int m, n;
int heights[105][105];
int fa[10005]; // 并查集数组，大小为 m*n

// 并查集查找（带路径压缩）
int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]); // 路径压缩：优化查询效率
}

// 并查集合并
void unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        fa[rootX] = rootY;
    }
}

int main() {
    // NOI 竞赛优化：加速输入输出
    ios::sync_with_stdio(false);
    cin.tie(0);

    if (!(cin >> m >> n)) return 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> heights[i][j];
        }
    }

    // 特判：1x1 矩阵
    if (m == 1 && n == 1) {
        cout << 0 << endl;
        return 0;
    }

    // 1. 初始化并查集
    for (int i = 0; i < m * n; i++) fa[i] = i;

    // 2. 将网格中的所有相邻关系转换为边
    vector<Edge> edges;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // 向右连边
            if (j + 1 < n) {
                int u = i * n + j;      // 将二维坐标 (i, j) 映射为一维编号
                int v = i * n + (j + 1);
                int w = abs(heights[i][j] - heights[i][j + 1]);
                edges.push_back({u, v, w});
            }
            // 向下连边
            if (i + 1 < m) {
                int u = i * n + j;
                int v = (i + 1) * n + j;
                int w = abs(heights[i][j] - heights[i + 1][j]);
                edges.push_back({u, v, w});
            }
        }
    }

    // 3. 按权值排序：O(E log E)
    sort(edges.begin(), edges.end());

    // 4. 依次加入边，直到起点和终点连通：O(E * alpha(V))
    int start_node = 0;
    int end_node = m * n - 1;

    for (const auto& edge : edges) {
        unite(edge.u, edge.v);
        // 核心检查：如果起点和终点已经在同一个连通块内
        if (find(start_node) == find(end_node)) {
            cout << edge.w << endl;
            return 0;
        }
    }

    return 0;
}

复杂度分析思考过程

1. 时间复杂度：

   • 建边：网格图中边数 $E \approx 2MN$。本题 $100 \times 100$，边数约 $20000$。
   • 排序：$O(E \log E)$，即 $20000 \log 20000 \approx 2.8 \times 10^5$。
   • 并查集循环：最坏情况下遍历所有边，每次 find 操作时间接近常数（反阿克曼函数）。
   • 总计：$O(MN \log(MN))$。对于 $100 \times 100$ 的规模，这在 NOI 评测机上大约只需要 10ms 左右。

2. 空间复杂度：

   • edges 数组：存储 $2MN$ 条边，占用 $O(MN)$。
   • fa 数组和 heights 数组：均为 $O(MN)$。
   • 结论：总空间约 1MB 左右，非常节省。

时间复杂度优化建议

• 路径压缩与按秩合并：代码中已经使用了路径压缩 fa[x] = find(fa[x])。如果追求极限速度，可以加入按秩合并（按树高或大小合并），使并查集操作完全达到 $O(\alpha(V))$。
• 坐标映射：在网格图中，将二维坐标转一维编号（r * n + c）是必备技巧，可以简化并查集和图论算法的编写。
• 排序优化：因为边权（高度差）最大只有 $10^6$，在边数极多（比如 $N, M=1000$）时，可以使用基数排序或计数排序将排序复杂度降至 $O(E)$。

读题关键词与题型总结

1. “最小化路径上的最大边权”：

   • 看到这个词直接联想：二分答案、并查集（Kruskal）、Dijkstra 变体。
   • 这类问题在 NOI 中被称为 “瓶颈路问题”。

2. “连通性判断”：

   • 如果题目问的是“是否存在一条路”，并查集是首选。
   • 如果题目问的是“最短是多少”，Dijkstra 或并查集均可。

3. 网格图的边数特征：

   • 网格图是典型的稀疏图，每个点只有 4 个邻居。
   • 在稀疏图中，邻接表和并查集的表现通常优于邻接矩阵。

总结

对于登山、修路、或者信号传输这类题目，只要代价定义为“路径上的最大跳跃高度”，这种 并查集动态加边 的方法往往是最符合直觉且最不容易在复杂逻辑（如优先级处理）上出错的方案。

为了帮助你构建高质量的 OJ 测试数据，我编写了这个数据生成器。它采用 Dijkstra 堆优化算法作为标程来生成 .out 文件，并设计了从基础边界到极限复杂度的 10 个测试点。

数据生成器代码 (C++14)

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cmath>
#include <string>
#include <random>
#include <ctime>
#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;

// --- 标程：Dijkstra 算法用于生成 .out 文件 ---
struct Node {
    int r, c, d;
    bool operator>(const Node& other) const { return d > other.d; }
};

int solve_std(int m, int n, const vector<vector<int>>& heights) {
    if (m == 0 || n == 0) return 0;
    vector<vector<int>> dist(m, vector<int>(n, INF));
    priority_queue<Node, vector<Node>, greater<Node>> pq;

    dist[0][0] = 0;
    pq.push({0, 0, 0});

    int dr[] = {0, 0, 1, -1};
    int dc[] = {1, -1, 0, 0};

    while (!pq.empty()) {
        Node curr = pq.top();
        pq.pop();

        if (curr.d > dist[curr.r][curr.c]) continue;
        if (curr.r == m - 1 && curr.c == n - 1) return curr.d;

        for (int i = 0; i < 4; i++) {
            int nr = curr.r + dr[i];
            int nc = curr.c + dc[i];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                int effort = max(curr.d, abs(heights[nr][nc] - heights[curr.r][curr.c]));
                if (effort < dist[nr][nc]) {
                    dist[nr][nc] = effort;
                    pq.push({nr, nc, effort});
                }
            }
        }
    }
    return 0;
}

// --- 数据写入函数 ---
void write_case(int id, int m, int n, const vector<vector<int>>& heights) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";

    ofstream fout(in_name);
    fout << m << " " << n << "\n";
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            fout << heights[i][j] << (j == n - 1 ? "" : " ");
        }
        fout << "\n";
    }
    fout.close();

    ofstream fans(out_name);
    fans << solve_std(m, n, heights) << endl;
    fans.close();
    cout << "Test Case " << id << " generated: " << m << "x" << n << endl;
}

int main() {
    mt19937 rng(time(0));
    auto get_rand = [&](int min_v, int max_v) {
        return uniform_int_distribution<int>(min_v, max_v)(rng);
    };

    // Case 1: 1x1 边界
    write_case(1, 1, 1, {{100}});

    // Case 2: 2x2 简单数据
    write_case(2, 2, 2, {{1, 2}, {3, 4}});

    // Case 3-4: 10x10 随机中等高度
    for (int id = 3; id <= 4; id++) {
        int m = 10, n = 10;
        vector<vector<int>> h(m, vector<int>(n));
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) h[i][j] = get_rand(1, 1000);
        write_case(id, m, n, h);
    }

    // Case 5: 100x1 极细长矩阵 (单向路径测试)
    {
        int m = 100, n = 1;
        vector<vector<int>> h(m, vector<int>(n));
        for (int i = 0; i < m; i++) h[i][0] = i * 2;
        write_case(5, m, n, h);
    }

    // Case 6: 100x100 平原 (体力消耗为 0)
    {
        vector<vector<int>> h(100, vector<int>(100, 500));
        write_case(6, 100, 100, h);
    }

    // Case 7: 100x100 阶梯梯度 (体力消耗为 1)
    {
        int m = 100, n = 100;
        vector<vector<int>> h(m, vector<int>(n));
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) h[i][j] = i + j;
        write_case(7, m, n, h);
    }

    // Case 8: 100x100 大规模随机
    {
        int m = 100, n = 100;
        vector<vector<int>> h(m, vector<int>(n));
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) h[i][j] = get_rand(1, 1000000);
        write_case(8, m, n, h);
    }

    // Case 9: 100x100 迷宫型 (强迫走长路)
    {
        int m = 100, n = 100;
        vector<vector<int>> h(m, vector<int>(n, 1000000));
        // 构造一条高度差为 1 的蛇形路径
        for (int i = 0; i < m; i++) {
            if (i % 2 == 0) {
                for (int j = 0; j < n; j++) h[i][j] = i + j;
            } else {
                h[i][(i / 2 % 2 == 0) ? n - 1 : 0] = i + 50; 
            }
        }
        write_case(9, m, n, h);
    }

    // Case 10: 100x100 极限随机 (测试 Dijkstra 堆性能)
    {
        int m = 100, n = 100;
        vector<vector<int>> h(m, vector<int>(n));
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) h[i][j] = get_rand(1, 1000000);
        write_case(10, m, n, h);
    }

    return 0;
}

数据生成器设计说明

1. 覆盖完整性：
   • Case 1 (1x1)：这是最容易忽略的边界，输出应为 0。
   • Case 5 (1x100)：测试程序对非方阵以及单向路径的处理。
   • Case 6-7：测试特殊地形（平原和均匀坡度）。
   • Case 9 (蛇形路径)：构造了一条极其深长的路径，且周围充满了“高墙”（高度差巨大），用来测试搜索算法（如未剪枝的 DFS）是否会超时，以及路径发现能力。
2. 文件大小优化：
   • 最大规模 $100 \times 100$ 的矩阵。每个数字加空格约 8 字节。
   • 每个 .in 文件约 $10000 \times 8 = 80$ KB。
   • 10 个测试点总大小约 0.8 MB，远低于 2MB 限制，便于在各类 OJ 平台快速上传和分发。
3. 效率与安全：
   • 标程使用非递归堆优化 Dijkstra。在 $100 \times 100$ 规模下，即使是构造的最复杂路径（Case 9），生成答案的时间也在毫秒级，不会导致数据生成超时。
   • 使用了 mt19937 随机数引擎，确保生成的随机数据具有良好的分布性。
4. 易错点预防：
   • 生成的坐标和高度均在 int 范围内（高度 $\le 10^6$）。
   • 在计算高度差时使用了 abs()，且在 Dijkstra 松弛时正确使用了 max() 逻辑。

如何使用

1. 将代码保存为 gen.cpp 并使用 g++ -O3 gen.cpp -o gen 编译。
2. 运行 ./gen。
3. 目录下会生成 1.in 到 10.out 共 20 个文件，这些就是标准的 OJ 测试数据。

在 NOI 竞赛中，处理“路径上最大边权的最小值”这类问题，通常有三种主流算法：二分答案+搜索、改造的 Dijkstra 以及 Kruskal 思想（并查集）。

下面我将从基础的二分搜索方案演进到竞赛中最常用的 Dijkstra 优化方案。

版本一：二分答案 + BFS (NOI 常用套路)

思路分析： 体力消耗值一定在 $[0, 10^6]$ 之间。如果我们设定一个阈值 $X$，只走高度差 $\le X$ 的边，判断是否能连通起点和终点。这个判断过程具有单调性：如果 $X$ 能通，那么 $X+1$ 一定也能通。 因此，我们可以对答案进行二分。

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>

using namespace std;

int m, n;
int heights[105][105];
bool vis[105][105];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

// 检查在体力消耗上限为 limit 的情况下，能否到达终点
bool check(int limit) {
    memset(vis, 0, sizeof(vis));
    queue<pair<int, int>> q;
    
    q.push({0, 0});
    vis[0][0] = true;
    
    while (!q.empty()) {
        pair<int, int> curr = q.front();
        q.pop();
        
        if (curr.first == m - 1 && curr.second == n - 1) return true;
        
        for (int i = 0; i < 4; i++) {
            int nx = curr.first + dx[i];
            int ny = curr.second + dy[i];
            
            // 越界检查、访问检查、以及体力消耗（高度差）检查
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && !vis[nx][ny]) {
                if (abs(heights[nx][ny] - heights[curr.first][curr.second]) <= limit) {
                    vis[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false); // NOI 比赛建议开启，加速 IO
    cin.tie(0);

    if (!(cin >> m >> n)) return 0;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> heights[i][j];

    // 二分答案的范围：高度差最小为 0，最大为 10^6
    int left = 0, right = 1000000, ans = 1000000;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (check(mid)) {
            ans = mid;    // 能通，尝试更小的体力值
            right = mid - 1;
        } else {
            left = mid + 1; // 不能通，必须增大体力值
        }
    }

    cout << ans << endl;
    return 0;
}

• 时间复杂度：$O(MN \log(\max\_height))$。其中 $MN$ 是 BFS 遍历的复杂度。
• 空间复杂度：$O(MN)$。用于存储 vis 数组和队列。

版本二：改造的 Dijkstra 算法 (最优复杂度)

思路分析： 普通 Dijkstra 求的是 $\min(\sum w)$，而本题求的是 $\min(\max(w))$。 我们定义 dist[i][j] 为到达点 (i, j) 所需的最小体力消耗。 更新准则：dist[邻居] = min(dist[邻居], max(dist[当前], 当前与邻居的高度差))。

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>

using namespace std;

const int INF = 0x3f3f3f3f;
int heights[105][105];
int dist[105][105];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

struct Node {
    int r, c, d;
    // 优先队列小根堆：d 越小优先级越高
    bool operator>(const Node& other) const {
        return d > other.d;
    }
};

int main() {
    int m, n;
    if (!(cin >> m >> n)) return 0;

    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> heights[i][j];

    // 初始化所有点体力消耗为无穷大
    memset(dist, 0x3f, sizeof(dist));
    dist[0][0] = 0;

    priority_queue<Node, vector<Node>, greater<Node>> pq;
    pq.push({0, 0, 0});

    while (!pq.empty()) {
        Node curr = pq.top();
        pq.pop();

        // 已经找到更小的消耗，剪枝
        if (curr.d > dist[curr.r][curr.c]) continue;
        if (curr.r == m - 1 && curr.c == n - 1) break;

        for (int i = 0; i < 4; i++) {
            int nr = curr.r + dx[i];
            int nc = curr.c + dy[i];

            if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                // 计算经过当前点到达邻居的体力消耗：取路径中差值的最大值
                int effort = max(curr.d, abs(heights[nr][nc] - heights[curr.r][curr.c]));
                if (effort < dist[nr][nc]) {
                    dist[nr][nc] = effort;
                    pq.push({nr, nc, effort});
                }
            }
        }
    }

    cout << dist[m - 1][n - 1] << endl;
    return 0;
}

• 时间复杂度：$O(MN \log(MN))$。对于 $100 \times 100$ 的数据，约为 $1.4 \times 10^5$ 次操作，性能极佳。
• 空间复杂度：$O(MN)$。

版本三：并查集（Kruskal 思想）

思路分析： 这种做法在 NOI 中非常高级，适合处理“最小化最大边权”问题。

1. 将网格中所有相邻格子的“高度差”看作一条边。
2. 将所有边按权值从小到大排序。
3. 依次将边加入并查集。当 (0, 0) 和 (m-1, n-1) 连通时，最后加入的那条边的权值即为答案。

时间复杂度优化建议与思考

1. 二分 vs Dijkstra：
   • 在网格图中，由于 $N, M$ 只有 100，二分搜索实现简单，不容易写挂。
   • 但如果 $N, M$ 增加到 $1000$，Dijkstra 的对数级复杂度优势将非常明显。
2. 常数优化：
   • 在 Dijkstra 中，如果从堆中弹出的点已经是终点，可以直接 break。
   • 使用 pair 或手写结构体比多次调用 max/abs 稍微快一点，但在 $100 \times 100$ 下不明显。
3. 空间优化：
   • 如果内存极其紧张，二分答案配合 DFS（手动模拟栈）可以省去队列的开销，但通常没有必要。

读题关键词总结

1. “最小化最大值” (Minimize the maximum effort)：这是典型的 二分答案 或 最短路变形 的标志。
2. “相邻格子高度差绝对值”：边权的定义。
3. “4 个方向”：网格图遍历的基本条件，确定方向数组。
4. “体力消耗定义”：明确体力消耗不是路径权重之和，而是路径上的单步最大值（这点非常容易看错）。

NOI 辅导建议

在草稿纸上引导学生时，应先画出 $2 \times 2$ 的小格子，手动模拟路径：

• 比如路径 $A \to B \to C$，边权分别是 3 和 1，那么这条路径的代价是 3（不是 4）。
• 这种代价计算方式决定了我们不能用普通的广搜找“最短”，而必须用“松弛”思想。