引水入城

形式化题目

给定一个 $N \times M$ 的海拔矩阵 $h$ 。定义供水规则：

第 1 行的每个格子本身就是一个"水源"，拥有自己的编号 $j$ （ $0 \leqslant j < M$ ）。
格子 $(i, j)$ 的可达源集合为：从第 1 行某个源出发，沿四邻方向每次走到一个海拔严格更低的相邻格子，最终能到达 $(i, j)$ 的那些源的编号集合；第 1 行的格子 $(0, j)$ 的可达源集合至少包含 $j$ 自身。

要求：

若第 $N$ 行每个格子的可达源集合都非空，输出 1，以及"选出最少的源，使得第 $N$ 行每格的可达源集合中至少含一个被选源"的最少源数；
否则输出 0，以及第 $N$ 行中可达源集合为空的格子数。

数据范围： $1 \leqslant N, M \leqslant 500$ ，海拔为正整数，时间限制 1000ms，内存限制 32MB。

正解

思路

朴素做法：对第 1 行的每个格子做一次 BFS/DFS，求出它能流到第 $N$ 行哪些列，得到 $M$ 个覆盖集合，再从中选最少的源。但这样是 $O(NM^2)$ ——对 $500 \times 500$ 的网格就是 $1.25 \times 10^8$ 次格子级操作，而且 $M$ 次 BFS 之间重复走了大量相同的路径，必须优化。

优化一：把"逐源 BFS"改成"按海拔降序的一遍 DP"。注意到水只从高处流向严格低处，格子 $(i, j)$ 能被哪些源供到，完全由它四邻中海拔严格更高的格子的供水源决定：

cover(i,j) = \bigl(\{j\} \text{ 若 } i=0 \text{，否则 } \varnothing\bigr) \cup \bigcup_{\text{邻居海拔} > h(i,j)} cover(\text{邻居})

把所有格子按海拔降序排序后逐格计算，每个格子在轮到它时，所有能流向它的更高邻居都已定型，一遍扫描就得到全图的可达源集合。海拔相同的邻居被严格不等号排除（水位不流动）。每个格子的"可达源集合"用 $M$ 位整数位集存储，合并就是按位或。

用样例 2（ $3 \times 6$ ）演示这个 DP。下表每格填的是该格可达源集合的位集（二进制，最低位对应源 0，从左到右列为列 $0..5$ ）：

行\列	列 0	列 1	列 2	列 3	列 4	列 5
第 1 行（海拔 8 4 5 6 4 4）	`000001`	`001111`	`001100`	`001000`	`011000`	`100000`
第 2 行（海拔 7 3 4 3 3 3）	`000001`	`001111`	`001100`	`001100`	`011000`	`100000`
第 3 行（海拔 3 2 2 1 1 2）	`000001`	`001111`	`001100`	`001100`	`111000`	`100000`

观察第 3 行：它的值不是独立算出来的，而是"每个格子 = 严格更高邻居的位集取并"。例如第 3 行列 4（海拔 1）的 111000 是由列 3（海拔 3，位集 001100）和列 5（海拔 2，位集 100000）合并而成；列 3 和列 4 海拔同为 1，互相不贡献。这也顺带完成了判定：第 3 行没有空位集，所以有解。

优化二：把"集合覆盖"化成"区间覆盖贪心"。一般集合覆盖是 NP 难的，但本题有一个关键性质：从一个源出发的水，流到第 $N$ 行的格子恰好是一段连续列区间。原因是可达集自上而下穿过每一行时的切口在列方向连续——流动只会让连续段增宽或平移，中间不会裂开（若裂开，缺口处的格子无法从两侧"跳"进来，跳入需要经过与两侧同层的格子，违反严格下降）。

于是把视角转置一下：不再问"列 $j$ 被哪些源供到"，而是问"源 $s$ 覆盖第 $N$ 行的哪些列"。对第 $N$ 行正扫一遍，源 $s$ 第一次出现的位置就是区间左端 $lo[s]$ ；反扫一遍同理得到右端 $hi[s]$ 。上面的表格转置后得到 6 个源点的区间：

源 $s$	0	1	2	3	4	5
覆盖区间 $[lo, hi]$	$[0,1]$	$[1,1]$	$[1,3]$	$[1,4]$	$[4,4]$	$[4,5]$

按左端排序后做经典区间覆盖贪心：维护已覆盖前缀 $[0, reach)$ ，每轮在所有左端 $\leqslant reach$ 的区间里选右端最大的，把 $reach$ 推进到那个右端 $+1$ 。样例的贪心过程：

轮次	已覆盖 $[0, reach)$	候选（左端 $\leqslant reach$ ）	选中	新 $reach$
1	$[0,0)$	$[0,1]$	$[0,1]$ （源 0）	$2$
2	$[0,2)$	$[1,1],[1,3],[1,4]$	$[1,4]$ （源 3）	$5$
3	$[0,5)$	$[4,4],[4,5]$	$[4,5]$ （源 5）	$6$

三轮覆盖完 $M=6$ 列，答案为 $3$ ，与样例 2 一致。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXM = 505;

int n, m;
int h[505][505];
bitset<MAXM> cover[505][505];   // cover[i][j]：格子 (i,j) 能被第 1 行哪些列的蓄水厂供到

struct Cell { int h, i, j; };
vector<Cell> order_;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> h[i][j];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            order_.push_back({h[i][j], i, j});
    sort(order_.begin(), order_.end(), [](const Cell& a, const Cell& b) { return a.h > b.h; });

    const int di[4] = {-1, 1, 0, 0};
    const int dj[4] = {0, 0, -1, 1};
    for (size_t idx = 0; idx < order_.size(); idx++) {
        int height = order_[idx].h, i = order_[idx].i, j = order_[idx].j;
        bitset<MAXM> bits;
        if (i == 0) bits.set(j);
        for (int d = 0; d < 4; d++) {
            int ni = i + di[d], nj = j + dj[d];
            if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
            if (h[ni][nj] > height) bits |= cover[ni][nj];
        }
        cover[i][j] = bits;
    }

    int unreachable = 0;
    for (int j = 0; j < m; j++)
        if (cover[n - 1][j].none()) unreachable++;
    if (unreachable) {
        cout << "0\n" << unreachable << "\n";
        return 0;
    }

    // 每个源点能供到的最后一行列是连续区间
    vector<int> lo(m, 0), hi(m, 0);
    bitset<MAXM> seen;
    for (int j = 0; j < m; j++) {
        bitset<MAXM> fresh = cover[n - 1][j] & ~seen;
        seen |= cover[n - 1][j];
        for (int s = 0; s < m; s++)
            if (fresh[s]) lo[s] = j;
    }
    seen.reset();
    for (int j = m - 1; j >= 0; j--) {
        bitset<MAXM> fresh = cover[n - 1][j] & ~seen;
        seen |= cover[n - 1][j];
        for (int s = 0; s < m; s++)
            if (fresh[s]) hi[s] = j;
    }

    vector<pair<int, int> > segments;
    for (int s = 0; s < m; s++)
        if (cover[n - 1][lo[s]][s])
            segments.push_back(make_pair(lo[s], hi[s]));
    sort(segments.begin(), segments.end());

    int built = 0, reach = 0, idx2 = 0;
    while (reach < m) {
        int best = reach;
        while (idx2 < (int)segments.size() && segments[idx2].first <= reach) {
            best = max(best, segments[idx2].second);
            idx2++;
        }
        built++;
        reach = best + 1;
    }
    cout << "1\n" << built << "\n";
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 08:58
# update_at: 2026-10-02 09:07

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    h = [[next(data) for _ in range(m)] for _ in range(n)]

    # cover[i][j]：格子 (i,j) 能被第 1 行哪些列的蓄水厂供到，用位集表示
    cover = [[0] * m for _ in range(n)]

    # 按海拔从高到低 DP：cover(低格) 由相邻更高格合并而来（水从高处流向低处）
    # 第 1 行格子的位集自带自己所在列，其余格子从空集开始向里并
    order = sorted(((h[i][j], i, j) for i in range(n) for j in range(m)), reverse=True)
    for height, i, j in order:
        # 第 1 行的格子自带蓄水厂，位集里永远包含自己所在的那一列
        bits = 1 << j if i == 0 else 0
        # 海拔相同的邻居互相流不通（水必须严格往低处走），只有严格更高的邻居贡献位集
        for ni, nj in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
            if 0 <= ni < n and 0 <= nj < m and h[ni][nj] > height:
                bits |= cover[ni][nj]
        cover[i][j] = bits

    # 只要有一个第 N 行格子不可达，统计这些格子的数量后直接输出无解
    last_row = cover[n - 1]
    unreachable = sum(1 for bits in last_row if bits == 0)
    if unreachable:
        print(0)
        print(unreachable)
        return

    # 经典区间覆盖贪心：每个源点能供到的第 N 行列是一段连续区间 [lo, hi]。
    # 注意 cover[n-1][j] 是"列 j 被哪些源供到"，要转置成"每个源覆盖哪些列"。
    # 两趟扫描：正扫第一次遇到的源记左端，反扫第一次遇到的源记右端。
    lo = [0] * m
    hi = [0] * m
    seen = 0
    for j in range(m):
        fresh = last_row[j] & ~seen                 # 本列新出现的源，当前列就是它们的左端
        seen |= last_row[j]
        while fresh:
            s = (fresh & -fresh).bit_length() - 1
            fresh &= fresh - 1
            lo[s] = j
    seen = 0
    for j in range(m - 1, -1, -1):
        fresh = last_row[j] & ~seen                 # 反向扫同理得到右端
        seen |= last_row[j]
        while fresh:
            s = (fresh & -fresh).bit_length() - 1
            fresh &= fresh - 1
            hi[s] = j

    segments = sorted((lo[s], hi[s]) for s in range(m) if last_row[lo[s]] >> s & 1)
    built = 0
    reach = 0                                         # 已覆盖到列 [0, reach)
    idx = 0
    while reach < m:
        best = reach                                   # 起点不越过 reach 的区间能伸到的最远右端
        while idx < len(segments) and segments[idx][0] <= reach:
            best = max(best, segments[idx][1])
            idx += 1
        built += 1
        reach = best + 1

    print(1)
    print(built)


if __name__ == "__main__":
    solve()

复杂度

时间：排序 $O(NM \log(NM))$ 主导，DP 与贪心为 $O(NM)$ 次位集操作、单次 $O(M/64)$ ，总计 $O(NM \log(NM) + NM \cdot M / 64)$ ，相比逐源 BFS 的 $O(NM^2)$ 大幅降低。
空间： $O(NM \cdot M / 64)$ 存位集矩阵。Python 大整数有额外对象开销，在 OJ 的 32MB 限制下有 MLE 风险（oj-python-style 允许）；同样的算法在 C++ 里用 bitset<500> 或 uint64_t 数组即可压到约 2MB。

总结

先判可解性：按海拔降序做一遍"可达源位集" DP，第 $N$ 行出现空位集即无解，空位集个数就是第二行答案。
有解时利用"每个源点在干旱区的覆盖是连续区间"这一性质，把集合覆盖化归为一维区间覆盖，贪心求最少蓄水厂数。
两个易错点：海拔相等的水不流动（严格不等号）；第 1 行格子的位集永远包含自己，DP 覆盖写时必须保留。

图示解析

无解情形长什么样

用一个 $2 \times 5$ 的小网格展示"水被高墙挡住"的典型结构（海拔标注在格内）：

	列 0	列 1	列 2	列 3	列 4
第 1 行	9	1	5	4	3
第 2 行	8	7（墙）	6	1	2

第 2 行列 0（海拔 8）唯一的更高邻居是第 1 行列 0（海拔 9），而列 1 的海拔 7 又比它高——水从列 0 进入后无法翻过海拔 7 向右推进，于是右侧若干列只能依赖别的水源；当某段干旱区上方完全被"更高的墙"封死时，这些格子的位集为空，本题输出 0 和不可达格数。这正是把"可达性判定"和"最少源数"放进同一遍 DP 的原因：判定信息（空位集）在 DP 结束时免费获得。

目录

形式化题目

正解

思路

代码

复杂度

总结

图示解析

无解情形长什么样