问题分析

我们需要在 $m \times n$ 的网格中放置最少的抽水机，使得所有城市格子（$x_{ij} > 0$）不被淹没。

关键规则：

• 水从高海拔向低海拔流动（四方向）
• 抽水机可以抽干所在格子的水
• 如果水能从某个抽水机位置流到城市格子，该城市就被保护

核心思路

问题转化

这实际上是一个连通性问题：我们需要选择最少的点（抽水机位置），使得所有城市格子都与至少一个抽水机在水能流动的路径上连通。

关键观察

水只能从高往低流，所以：

• 相同海拔的格子可以互相流通
• 高海拔的格子可以流向低海拔的格子
• 低海拔的格子不能流向高海拔的格子

算法设计

并查集 + 按海拔排序

1. 初始化：用并查集维护连通块
2. 按海拔从低到高处理：
   • 相同海拔的格子先合并
   • 从低海拔向高海拔合并相邻格子
   • 当遇到城市格子时，检查是否需要新增抽水机

算法流程

步骤1：数据预处理

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        read(a[i][j]), p[++cnt] = {(int)abs(a[i][j]), i, j, a[i][j] > 0};
sort(p + 1, p + 1 + cnt);  // 按海拔排序

步骤2：合并相同海拔的连通块

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        for (int k = 1; k <= 4; k++) {
            int xx = i + fx[k], yy = j + fy[k];
            if (abs(a[i][j]) == abs(a[xx][yy]))
                t.merge(i, j, xx, yy);  // 合并相同海拔
        }

步骤3：按海拔从低到高处理

for (int i = 1; i <= cnt; i++) {
    int x = p[i].x, y = p[i].y;
    
    // 海拔变化时，处理上一批城市格子
    if (p[i].h != p[i - 1].h) {
        for (int j : vt)
            if (a[p[j].x][p[j].y] > 0)
                t.add(p[j].x, p[j].y);  // 尝试标记城市格子
        vt.clear();
    }
    
    // 合并到低海拔邻居
    for (int j = 1; j <= 4; j++) {
        int xx = x + fx[j], yy = y + fy[j];
        if (abs(a[x][y]) <= abs(a[xx][yy])) continue;
        t.merge(x, y, xx, yy);  // 从高往低合并
    }
    
    vt.push_back(i);
}

并查集实现细节

class BIT {
private:
    int fa[maxn * maxm];
    bool have[maxn * maxm];  // 标记连通块是否已有抽水机
public:
    int find_root(int x) {
        return fa[x] == 0 ? x : fa[x] = find_root(fa[x]);
    }
    
    void merge(int x, int y, int xx, int yy) {
        x = find_root(x * (m + 1) + y);
        xx = find_root(xx * (m + 1) + yy);
        if (x == xx) return;
        have[xx] |= have[x];  // 继承抽水机状态
        fa[x] = xx;
    }
    
    void add(int x, int y) {
        int root = find_root(x * (m + 1) + y);
        if (have[root]) return;  // 已有抽水机
        have[root] = 1, ans++;   // 新增抽水机
    }
};

算法正确性分析

为什么按海拔从低到高处理？

• 水从高往低流，所以低海拔区域先被影响
• 当处理到某个海拔时，所有比它低的区域已经处理完毕
• 这样可以保证水流通路的完整性

为什么这样能得到最少抽水机？

• 每个连通块最多需要一个抽水机
• 当连通块中出现城市格子时，如果还没有抽水机，就新增一个
• 通过并查集的合并，自动复用已有的抽水机

复杂度分析

• 时间复杂度：$O(mn \log(mn))$
  • 排序：$O(mn \log(mn))$
  • 并查集操作：近似 $O(mn \alpha(mn))$
• 空间复杂度：$O(mn)$

样例验证

对于样例输入，算法过程：

1. 找到海拔最低的区域，建立连通块
2. 按海拔递增处理，合并连通块
3. 当遇到城市格子时检查是否需要抽水机
4. 最终得到需要2个抽水机

总结

本题的关键在于将洪水流动问题转化为图论中的连通性问题，通过并查集维护水流通路，按海拔排序确保正确的合并顺序。这种"排序+并查集"的思路在解决涉及优先级或依赖关系的连通性问题时非常有效。