原题链接

原题有一句话是：Of course, the communicating tubes principle makes its work, so draining one square results in lowering the water level or complete draining of those squares from which the water can flow down to the one with the pump。

感觉新题面完全没法体现这一点。

理解到这句话后，题目是简单的。

考虑贪心，从海拔最低的方格开始考虑。

处理到每个方格时，将其与周围可以流水的方格连边。

此时若这个连通块内存在一个抽水器，则这个方格的水会被处理。

否则，若这个方格是一个农田，则需要在这里放一个抽水器。

#include <bits/stdc++.h>
using namespace std;

static const int32_t dx[] = {0, 0, -1, 1};
static const int32_t dy[] = {-1, 1, 0, 0};

struct Dsu {
  vector<int8_t> tag;
  vector<size_t> fa;

  Dsu(size_t n) : tag(n, 0), fa(n) { iota(fa.begin(), fa.end(), 0); }
  void mark(size_t x) { tag[getf(x)] = true; }
  bool get_mark(size_t x) { return tag[getf(x)]; }
  size_t getf(size_t x) { return x == fa[x] ? x : fa[x] = getf(fa[x]); }
  void merge(size_t x, size_t y) {
    x = getf(x), y = getf(y);
    tag[y] |= tag[x], fa[x] = y;
  }
};

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  size_t n, m;
  cin >> n >> m;

  vector<vector<bool>> farm(n, vector<bool>(m));
  vector<vector<int32_t>> height(n, vector<int32_t>(m));
  map<int32_t, vector<pair<size_t, size_t>>> query;
  for (size_t i = 0; i < n; ++i)
    for (size_t j = 0; j < m; ++j) {
      cin >> height[i][j];
      if (height[i][j] > 0)
        farm[i][j] = true;
      else
        height[i][j] = -height[i][j];
      query[height[i][j]].emplace_back(i, j);
    }

  size_t ans = 0;
  Dsu dsu(n * m);
  auto getid = [&](size_t i, size_t j) { return i * m + j; };

  for (const auto &v : query) {
    for (const auto &[i, j] : v.second) {
      for (size_t k = 0; k < 4; ++k) {
        size_t x = i + dx[k], y = j + dy[k];
        if (x < n && y < m && height[x][y] <= height[i][j])
          dsu.merge(getid(i, j), getid(x, y));
      }
    }
    for (const auto &[i, j] : v.second) {
      size_t u = getid(i, j);
      if (farm[i][j] && !dsu.get_mark(u)) {
        ++ans, dsu.mark(u);
      }
    }
  }
  cout << ans << '\n';
  return 0;
}