题解：P7250 [BalticOI 2012 Day1] 山峰

传送门

思路简述

题目中的输出格式很明显的提醒我们要把这道题分为两个部分：找到所有的山峰，以及求出走到海拔更高的山峰所经过的最低海拔最大值。接下来的题解也会以这两个部分分开来讲述。

第一部分

我们注意到，一个山峰是一个周围没有海拔比它高的连通块，我们不难想到用并查集维护这一点。我们对于每一个方格，遍历与它联通的方格所在的连通块，根据连通块所在的情况来更新状态。具体而言，若旁边的方格海拔比他高，那么当前方格所在的连通块必不可能是山峰；若旁边的方格与它的海拔相同，就合并两个连通块，同时更新联通块是否可能是山峰。代码如下：

// 初始化：ispeak （代表当前连通块是否可能是山峰） 全为真，每个方格的父亲为它本身。
// 由于采用的是一维的输入方式，getid(x, y) 表示找到 (x, y) 在一维数组中的位置。
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 (nx < 1 || nx > n || ny < 1 || ny > m) continue;
      if (a[getid(nx, ny)] > a[getid(i, j)])
        ispeak[find(getid(i, j))] = false; // 不可能是山峰
      else if (a[getid(nx, ny)] == a[getid(i, j)]) {
        // 合并，通过两个连通块的状态更新状态
        int fx = find(getid(nx, ny)), fy = find(getid(i, j));
        if (fx != fy) ispeak[fy] = ispeak[fx] && ispeak[fy], fa[fx] = fy;
      }
    }
  }
}

当然，我们要给不同的山峰打上不同的标记记录下来，代码如下：

  for (int i = 1; i <= n * m; ++i) {
  int ff = find(i); // 连通块编号
  if (!vis[ff] && ispeak[ff]) // 记录下每个山峰的连通块编号，并打上标记
      peak[++tot] = ff, rev[ff] = tot;
  vis[ff] = true;
}
  for (int i = 1; i <= n * m; ++i)
    has[i] = rev[find(i)]; // 记录每个方格处于哪个山峰中

求出 has 数组之后，我们就可以去求每个山峰走到海拔更高的山峰所经过的最低海拔最大值。

第二部分

我们考虑按照海拔排序，从大到小在图上加入方格，通过对图的连通性的实时维护求出答案。我们考虑再一次使用并查集。我们需要明确 has 数组在这一部分的定义：在这一个连通块内还没有得到答案的山峰编号。假设新合并的两个连通块所剩的山峰高度不同，那么可以直接得出较矮的山峰的答案，那么合并后的 has 值只剩下了高的那个山峰；但如果两个山峰海拔相同呢？我们当然可以把数组换成 vector，搞启发式合并，但我采取的是另一种方法：对于山峰的编号也开一个并查集，在这种情况时直接在并查集上合并即可。理清了思路，我们可以写出以下的合并函数：

il void merge(int x, int y, int d) {
  x = find(x), y = find(y); // 连通块的并查集
  if (x == y) return ;
  int nx = find2(has[x]), ny = find2(has[y]); // 山峰编号的并查集
  if (a[peak[nx]] == a[peak[ny]]) {
    fa[x] = y, fa2[nx] = ny;
    return ;
  }
  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;
  return ;
}

那么我们只需要不段的加入方格，实时更新连通性即可：

for (int i = 1; i <= n; ++i) {
  for (int j = 1; j <= m; ++j) {
    b[getid(i, j)] = (node){a[getid(i, j)], i, j};
  }
}
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 (nx < 1 || nx > n || ny < 1 || ny > m || a[getid(nx, ny)] < v) continue;
    merge(getid(x, y), getid(nx, ny), v);
  }
}

最后就可以愉快的统计答案了，排序输出即可。

代码

由于模拟赛时代码较长（有着极长的无用头文件），代码放在了剪贴板 中。