「BalticOI 2012 Day1」山峰 题解

题目分析

这个问题要求找出岛屿上的所有山峰，并为每座山峰计算前往更高山峰时路径上最低点的最大海拔值。

关键定义

• 山峰：一个平坦区域（海拔相同的连通区域），且不与任何海拔更高的平坦区域相邻
• 路径最低点：从当前山峰到更高山峰的路径中海拔的最低值
• 目标：对于每个山峰，找到所有可能路径中最低点的最大值

算法思路

1. 山峰检测

使用并查集将海拔相同的相邻点合并为平坦区域，然后标记那些不与更高海拔区域相邻的平坦区域为山峰。

2. 关键观察

从高海拔到低海拔处理网格点，在合并过程中维护每个山峰组件能到达的最低点信息。

3. 并查集优化

使用两层并查集结构：

• 第一层：合并相同海拔的网格点
• 第二层：合并山峰组件，在合并时更新答案

核心算法

山峰识别

// 合并相同海拔的相邻区域
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        for (int k = 0; k < 8; ++k) {
            int nx = i + dx[k], ny = j + dy[k];
            if (a[getid(nx, ny)] == a[getid(i, j)]) {
                // 合并相同海拔区域
            }
        }
    }
}

// 标记山峰（不与更高区域相邻的平坦区域）
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        for (int k = 0; k < 8; ++k) {
            int nx = i + dx[k], ny = j + dy[k];
            if (a[getid(nx, ny)] > a[getid(i, j)])
                ispeak[find(getid(i, j))] = false;
        }
    }
}

答案计算

// 按海拔降序处理所有点
std::sort(b + 1, b + 1 + n * m);

for (int i = 1; i <= n * m; ++i) {
    int v = b[i].v, x = b[i].x, y = b[i].y;
    
    for (int j = 0; j < 8; ++j) {
        int nx = x + dx[j], ny = y + dy[j];
        if (a[getid(nx, ny)] >= v) {
            merge(getid(x, y), getid(nx, ny), v);
        }
    }
}

合并策略

void merge(int x, int y, int d) {
    x = find(x), y = find(y);
    int nx = find2(has[x]), ny = find2(has[y]);
    
    if (a[peak[nx]] == a[peak[ny]]) {
        // 相同海拔山峰合并
        fa2[nx] = ny;
    } else if (a[peak[nx]] > a[peak[ny]]) {
        // 高海拔山峰吸收低海拔区域
        ans[ny] = max(ans[ny], d);
        fa[y] = x;
    } else {
        // 低海拔山峰被高海拔吸收
        ans[nx] = max(ans[nx], d);
        fa[x] = y;
    }
}

复杂度分析

• 空间复杂度：$O(N \times M)$，存储网格和并查集结构
• 时间复杂度：$O(N \times M \times \alpha(N \times M))$，其中 $\alpha$ 是反阿克曼函数
• 排序复杂度：$O(N \times M \log(N \times M))$

算法标签

🏷️ 主要算法

并查集 (Union-Find)

• 两层并查集结构管理连通性
• 路径压缩优化查找效率

离线处理 (Offline Processing)

• 按海拔降序处理网格点
• 在合并过程中动态维护答案

🏷️ 图论算法

连通分量 (Connected Components)

• 8方向连通性检测
• 平坦区域的连通块识别

组件合并 (Component Merging)

• 基于海拔高度的组件合并策略
• 在合并时传递最低点信息

🏷️ 数据结构

排序预处理 (Sorting Preprocessing)

• 网格点按海拔降序排列
• 确保从高到低的处理顺序

答案传递 (Answer Propagation)

• 在并查集合并时更新答案
• 维护每个山峰组件的最佳路径信息

🏷️ 问题类型

图上的动态连通性 (Dynamic Connectivity on Grid)

• 在网格图上维护连通关系
• 支持按特定顺序的合并操作

最优化问题 (Optimization Problem)

• 寻找路径最低点的最大值
• 通过组件合并传递最优解

这个问题的核心在于利用并查集按海拔降序处理网格点，在组件合并过程中维护路径信息，体现了离线处理在解决复杂连通性问题中的强大能力。