[NOIP 2010 提高组] 引水入城

GitHub跳转原题关系图返回列表

把“水往低处流”看成有向图的可达性，每个蓄水厂一次 BFS 求出它能灌溉的干旱区城市；可行时这个集合恰好是一段连续区间，于是问题化为区间覆盖贪心。

OJ: luogu

题目 ID: P1514

难度:提高

标签:BFS图论网格贪心区间覆盖可达性

创建: 2026-10-02 09:05

更新: 2026-10-03 10:50

形式化题目

有一个 $N$ 行 $M$ 列的网格，第 $i$ 行第 $j$ 列的格子有海拔 $h_{i,j}$ 。

只有第 $1$ 行的格子允许“建造蓄水厂”。一个格子有水，当且仅当：

它自己建了蓄水厂；或者
存在一个与它共边相邻、海拔严格更高、并且已经有水的格子。

要求第 $N$ 行的每个格子都有水。如果做不到，就数出第 $N$ 行中有多少个格子不可能有水。

把每个格子看成结点，若 $u,v$ 相邻且 $h_u > h_v$ ，连一条有向边 $u \to v$ 。因为水只能往低处流，海拔沿任何一条路径都严格递减，所以这张有向图没有环（是 DAG）。

于是：

格子 $v$ 有水 $\iff$ 存在第 $1$ 行的某个格子 $s$ ，使得 $s$ 在有向图上可以到达 $v$ 。

问题变成：最少选第 1 行的几个结点，使它们能到达第 $N$ 行的全部结点；做不到时统计第 $N$ 行中无法被任何第 1 行结点到达的结点数。

暴力解法

思路

最直接的做法就是把“建哪些蓄水厂”这件事全部枚举一遍。

第 $1$ 行一共有 $M$ 座城市，每座城市只有两种决策——建蓄水厂、或者不建。用 01 序列来表示：

choose[j] = 1：在第 1 行第 $j$ 列建蓄水厂；
choose[j] = 0：不建。

dfs_choose(dep) 只负责填写第 dep 座城市的决策，填满 choose[1..M] 以后，在叶子节点上做一次统一的检查：把所有 choose[j] == 1 的格子当作起点，一起做一次洪水填充（只往海拔更低的相邻格子走），看看第 $N$ 行是不是每一列都被填到。

全部通水，就用建站数量去更新答案的最小值；
一遍枚举下来一个合法方案都没有，就说明无解。此时把“每座城市都建站”这个最强方案拿出来统计第 $N$ 行还剩下几座通不了水的城市。

“先生成完整的 choose[]，再在叶子节点统一检查”把枚举和判定分得很干净： $2^M$ 条选择序列一条不漏，所以答案一定正确。

代码

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117/**
 * 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-03 10:35
 * update_at: 2026-10-03 10:35
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 使用 01 序列 / 选择序列递归枚举所有可能：
//   第一行一共有 m 座城市，每座城市的决策只有两种——建蓄水厂或不建。
//   choose[j] = 1 表示在第 1 行第 j 列建蓄水厂，0 表示不建。
//   dfs_choose(dep) 只负责填写第 dep 座的决策，填满 choose[1..m] 后
//   在叶子节点统一做一次多源洪水填充，检查干旱区是否全部通水。
// 枚举 2^m 种方案，只有 m 很小时可用，所以只适合小数据对拍。
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 64; // 允许小规模生成器造到 n = 60；对拍时 m 会控制在 14 以内

int n, m;
int h[MAXN][MAXN];    // 海拔高度
int choose[MAXN];     // choose[j]：第 1 行第 j 列是否建蓄水厂
int seen[MAXN][MAXN]; // 洪水填充的访问标记
int able[MAXN];       // 干旱区第 j 列是否通水
int ans;              // 最少蓄水厂数量

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

// 从 (x, y) 出发把能流到的城市全部标记；到第 n 行就记录通水。
void flood(int x, int y) {
    seen[x][y] = 1;
    if (x == n) able[y] = 1;

    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d];
        int ny = y + dy[d];
        if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
        if (seen[nx][ny]) continue;
        if (h[nx][ny] >= h[x][y]) continue; // 水往低处流
        flood(nx, ny);
    }
}

// 检查当前 choose[] 是否能让干旱区全部通水。
// 能通水时返回蓄水厂数量，不能通水时返回 -1。
int check() {
    int cnt = 0;
    for (int j = 1; j <= m; j++) {
        cnt += choose[j];
    }
    if (cnt == 0) return -1; // 一个蓄水厂都没有，不可能通水

    memset(seen, 0, sizeof(seen));
    memset(able, 0, sizeof(able));
    for (int j = 1; j <= m; j++) {
        if (choose[j] == 1) flood(1, j);
    }

    for (int j = 1; j <= m; j++) {
        if (able[j] == 0) return -1;
    }
    return cnt;
}

// 每一层决定第 dep 座城市建不建蓄水厂。
void dfs_choose(int dep) {
    if (dep == m + 1) {
        int cnt = check();
        if (cnt != -1 && cnt < ans) ans = cnt;
        return;
    }

    for (int v = 0; v <= 1; v++) {
        choose[dep] = v;
        dfs_choose(dep + 1);
    }
}

void read_input() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> h[i][j];
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();

    ans = MAXN * MAXN; // 一个肯定取不到的初值
    dfs_choose(1);

    if (ans < MAXN * MAXN) {
        cout << 1 << "\n" << ans << "\n";
        return 0;
    }

    // 无解：把全部城市都建成蓄水厂，数一数干旱区里还有多少座通不了水。
    for (int j = 1; j <= m; j++) choose[j] = 1;
    memset(seen, 0, sizeof(seen));
    memset(able, 0, sizeof(able));
    for (int j = 1; j <= m; j++) flood(1, j);

    int bad = 0;
    for (int j = 1; j <= m; j++) {
        if (able[j] == 0) bad++;
    }
    cout << 0 << "\n" << bad << "\n";

    return 0;
}

复杂度

枚举 $2^M$ 条选择序列，每条做一次 $O(NM)$ 的洪水填充，总时间复杂度 $O(2^M\cdot NM)$ ，空间复杂度 $O(NM)$ 。

瓶颈

瓶颈完全在 $2^M$ 的枚举上， $M = 20$ 就已经很难受了，而题目的 $M$ 最大到 $500$ 。所以暴力只能当小数据的对拍基线。

真正的浪费在于：枚举的所有方案里，同一个蓄水厂能灌溉的城市是不变的，但暴力对每种方案都重新算了一遍。只要先独立算出“在每个位置建站能灌溉哪些城市”，方案之间的共享信息就出来了。

正解

思路

第一步：每个蓄水厂一次 BFS

固定在第 1 行第 $j$ 列建一个蓄水厂，从 $(1,j)$ 出发做一次 BFS，只允许走相邻且海拔严格更低的格子，访问到的所有格子就是“水能流到的地方”。其中位于第 $N$ 行的那些列，就是这座蓄水厂能灌溉的干旱区城市。

对 $M$ 个源头各做一次，就得到了 $M$ 个集合 $S_1, S_2, \dots, S_M$ 。这一步把暴力里被重复计算 $2^M$ 次的东西，变成只算 $M$ 次。

第二步：判断能不能做到

“能满足要求” $\iff$ “第 $N$ 行的每一列都属于某个 $S_j$ ”。

所以把所有 $S_j$ 并起来，数一数第 $N$ 行里没被覆盖的列数，就是无解时的答案。这一步和暴力解里的判断方式完全一样，不需要任何额外性质。

第三步：可行时，每个 $S_j$ 是一段连续区间

接下来要解决的是“用最少的 $S_j$ 盖住第 $N$ 行”。如果 $S_j$ 是任意的集合，这就是 NP-hard 的集合覆盖问题；但本题有一个关键性质：

引理：若整体可行，那么对每个源头 $j$ ， $S_j$ 一定是第 $N$ 行上一段连续的区间，即
$S_j = [l_j,\ r_j]$
的形式。

为什么？ 反设源头 $s$ 能到 $(N,a)$ 和 $(N,c)$ （ $a < c$ ），却到不了中间的 $(N,b)$ （ $a < b < c$ ）。

取一条从 $(1,s)$ 到 $(N,a)$ 的下坡路径 $P_1$ ，和一条从 $(1,s)$ 到 $(N,c)$ 的下坡路径 $P_2$ ；
因为整体可行， $(N,b)$ 被某个源头 $t$ 覆盖，存在一条从 $(1,t)$ 到 $(N,b)$ 的下坡路径 $Q$ ；
$Q$ 不能碰到 $P_1$ 或 $P_2$ 上的任何一个格子。否则设公共格为 $u$ ，则 $s$ 能到 $u$ （因为 $u$ 在 $P_1$ 或 $P_2$ 上），而 $u$ 又能沿 $Q$ 的后半段到 $(N,b)$ ，于是 $s$ 能到 $(N,b)$ ，与反设矛盾；
但把 $Q$ 看成一条从上边界（ $(1,t)$ ）通到下边界（ $(N,b)$ ）的路径，它像一堵竖墙把棋盘分成左右两半。若 $t < s$ ，则起点 $(1,s)$ 在墙右侧、终点 $(N,a)$ 在墙左侧， $P_1$ 必须穿墙；若 $t > s$ ，则 $P_2$ 必须穿墙；若 $t = s$ ，那么 $(1,s)$ 本身就在 $Q$ 上，直接矛盾。三种情况都会让某条路径与 $Q$ 相交。

矛盾说明 $(N,b)$ 一定在 $S_s$ 里， $S_s$ 中间不会有空洞。

这个引理只在可行的前提下成立。不可行时集合完全可以断开，例如

text

1
22 2 2 4 3
1 4 1 4 2

第 1 行第 4 列（海拔 4）能流到第 2 行的第 3 列和第 5 列，却到不了第 4 列：第 2 行第 4 列海拔也是 4，四周没有严格更高的邻居，任何源头都到不了它，所以整张图本来就不可行。算法会先在第二步拦下这种数据，根本不会用到这个引理。

第四步：区间覆盖贪心

可行性确认后， $S_j$ 就是区间 $[l_j,r_j]$ ，问题化为：用最少的区间覆盖 $[1,M]$ 。

标准贪心：把所有非空区间按左端点升序排序。设当前还差 $[pos, M]$ 没有被覆盖：

在所有满足 $l_j \leqslant pos$ （能接上当前缺口）的区间里，选右端点 $r_j$ 最大的那个；
这个区间必须选——位置 $pos$ 只能被左端点 $\leqslant pos$ 的区间覆盖；而在这些区间里，右端点越远，一次能盖住的城市越多，显然最划算；
令 $pos \gets far + 1$ （ $far$ 是选中的右端点），重复，直到 $pos > M$ 。

为什么步骤 1 不能简化成“取左端点最小的可接区间”？ 因为右端点才是决定“这一刀能砍多远”的量。例如还差 $[3,6]$ ，可选区间有 $[2,4]$ 和 $[2,5]$ ，取前者会白多用一个区间。

样例 2 的完整推演

样例 2 的网格是

text

1
2
3行1: 8 4 5 6 4 4
行2: 7 3 4 3 3 3
行3: 3 2 2 1 1 2

对第 1 行每一列做一次 BFS，得到 6 个覆盖集合：

源列 $j$	行 1 海拔	能灌溉的干旱区列 $S_j$	区间 $[l_j,r_j]$
1	8	$\{1,2\}$	$[1,2]$
2	4	$\{2\}$	$[2,2]$
3	5	$\{2,3,4\}$	$[2,4]$
4	6	$\{2,3,4,5\}$	$[2,5]$
5	4	$\{5\}$	$[5,5]$
6	4	$\{5,6\}$	$[5,6]$

六个集合的并集是 $\{1,2,3,4,5,6\}$ ，说明可行。按左端点排序后贪心：

步骤	待覆盖位置 $pos$	能接上的区间	选中（源头）	$pos$ 更新为
1	$1$	$[1,2]$	$[1,2]$ （源 1）	$3$
2	$3$	$[2,2],\ [2,4],\ [2,5]$	$[2,5]$ （源 4）	$6$
3	$6$	$[5,5],\ [5,6]$	$[5,6]$ （源 6）	$7 > 6$ ，结束

答案是 $3$ ，选源 $1,4,6$ ，正好与题面样例说明图里粗线框出的 3 座城市一致。注意第 1 步之后 $pos = 3$ ，而源 3、源 4 的区间左端点是 $2 \leqslant 3$ ，仍然可以参与第 2 步的挑选——这正是“在所有能接上的区间里挑右端点最远的”这一步的意义。

代码

flood(int sy) 对第 1 行第 sy 列做一次 BFS，同时记录它覆盖到的最左、最右干旱区列；主函数先判可行性，再跑区间覆盖贪心。

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139/**
 * 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-03 10:35
 * update_at: 2026-10-03 10:35
 */
// P1514 [NOIP 2010 提高组] 引水入城
// 思路：
//   1. 水只能从高处流向低处，把一个城市有水的效果看成“从第 1 行某座城市出发，
//      沿着只往低处走的有向边能到达哪些城市”。
//   2. 所以第 1 行每座城市都当作一次 BFS 的源，算出它能灌溉的干旱区城市。
//      干旱区里任何一座都没被覆盖，方案就不存在，直接输出 0 和不可能通水的城市数。
//   3. 若所有干旱区城市都能被覆盖，则每个蓄水厂能覆盖的干旱区城市恰好是
//      连续的一段（关键性质，见题解证明），于是问题变成“用最少的区间覆盖 [1, m]”，
//      按左端点排序后贪心即可。
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

const int MAXN = 505;
const int MAXC = MAXN * MAXN;

int n, m;
int h[MAXN][MAXN];     // h[i][j]：第 i 行第 j 列城市的海拔高度
int seen[MAXN][MAXN];  // 当前这次 BFS 的访问标记：值等于 stamp 表示本次访问过
int stamp;             // BFS 时间戳，递增后就不用每次清空 seen 数组
int able[MAXN];        // able[j]：干旱区第 j 列是否被某个蓄水厂覆盖
int segL[MAXN];        // 第 1 行第 j 列建蓄水厂时，覆盖的干旱区列区间左端点
int segR[MAXN];        // 右端点；区间为空时 segL = m + 1、segR = 0
int qx[MAXC], qy[MAXC]; // 手写 BFS 队列，存城市坐标

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

// 从第 1 行第 sy 列的城市建一个蓄水厂出发做 BFS，
// 求出它实际上能灌溉到的干旱区城市列区间 [segL[sy], segR[sy]]。
// 能通水的干旱区城市同时标进 able[]。
void flood(int sy) {
    stamp++;
    int head = 0, tail = 0;
    qx[tail] = 1;
    qy[tail] = sy;
    tail++;
    seen[1][sy] = stamp;

    int left = m + 1; // 覆盖到的最右小列
    int right = 0;    // 覆盖到的最右列

    while (head < tail) {
        int x = qx[head];
        int y = qy[head];
        head++;

        if (x == n) { // 走到第 n 行，说明这座干旱区城市可以通水
            if (y < left) left = y;
            if (y > right) right = y;
            able[y] = 1;
        }

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
            if (seen[nx][ny] == stamp) continue;
            if (h[nx][ny] >= h[x][y]) continue; // 水只能由高处流向低处
            seen[nx][ny] = stamp;
            qx[tail] = nx;
            qy[tail] = ny;
            tail++;
        }
    }

    segL[sy] = left;
    segR[sy] = right;
}

void read_input() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> h[i][j];
        }
    }
}

void solve() {
    for (int j = 1; j <= m; j++) {
        flood(j);
    }

    // 干旱区中一座城市如果没有任何蓄水厂能覆盖，方案就不存在。
    int bad = 0;
    for (int j = 1; j <= m; j++) {
        if (able[j] == 0) bad++;
    }
    if (bad > 0) {
        cout << 0 << "\n" << bad << "\n";
        return;
    }

    // 可行时每个蓄水厂覆盖的干旱区城市是一段连续区间，
    // 收集所有非空区间，按左端点排序。
    vector<pair<int, int> > seg;
    for (int j = 1; j <= m; j++) {
        if (segL[j] <= segR[j]) {
            seg.push_back(make_pair(segL[j], segR[j]));
        }
    }
    sort(seg.begin(), seg.end());

    // 贪心：下一个待覆盖的城市是 pos，在左端点不超过 pos 的区间里挑右端点最远的。
    int ans = 0;
    int pos = 1;
    int i = 0;
    while (pos <= m) {
        int far = pos - 1;
        while (i < (int)seg.size() && seg[i].first <= pos) {
            if (seg[i].second > far) far = seg[i].second;
            i++;
        }
        ans++;
        pos = far + 1;
    }

    cout << 1 << "\n" << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

复杂度

对 $M$ 个源头各做一次 $O(NM)$ 的 BFS，共 $O(NM\cdot M)$ ；贪心排序 $O(M\log M)$ 。空间复杂度 $O(NM)$ 。

$N = M = 500$ 时约为 $1.25\times10^8$ 次松弛，实测约 $0.2$ 秒。

总结

这道题的解法是一条清晰的“先建图、再降维”的链路：

建模：“水往低处流” $\Rightarrow$ 相邻且更矮的方向连边 $\Rightarrow$ 一个 DAG 上的可达性问题。于是“某座城市有没有水”变成“它能不能被某个源头到达”。
去重：暴力枚举方案时，同一个蓄水厂能灌溉的城市被反复重算。改成对每个源头独立做一次 BFS， $2^M$ 次计算被压缩成 $M$ 次。
降维：一般的“最少集合覆盖”是 NP-hard，但可行时每个 $S_j$ 都是数轴上的连续区间，于是退化成经典的区间覆盖贪心。
贪心：按左端点排序，每次在能接上当前缺口的区间里选右端点最远的一个。

其中第 3 步是全题的关键：它不仅给出算法，也解释了为什么“不可行”和“可行”必须分成两个分支——连续区间性质只在可行时成立。而判断可行性本身只用一次简单的并集统计，代价极低。

P1514 [NOIP 2010 提高组] 引水入城

题目背景

NOIP2010 提高组 T4

题目描述

在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个 $N$ 行 $M$ 列的矩形，如上图所示，其中每个格子都代表一座城市，每座城市都有一个海拔高度。

为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。

因此，只有与湖泊毗邻的第 $1$ 行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前提，是存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。由于第 $N$ 行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干旱区中不可能建有水利设施的城市数目。

输入格式

每行两个数，之间用一个空格隔开。输入的第一行是两个正整数 $N,M$ ，表示矩形的规模。接下来 $N$ 行，每行 $M$ 个正整数，依次代表每座城市的海拔高度。

输出格式

两行。如果能满足要求，输出的第一行是整数 $1$ ，第二行是一个整数，代表最少建造几个蓄水厂；如果不能满足要求，输出的第一行是整数 $0$ ，第二行是一个整数，代表有几座干旱区中的城市不可能建有水利设施。

输入输出样例 #1

输入 #1

text

输出 #1

text

1
21
1

输入输出样例 #2

输入 #2

text

1
2
3
43 6
8 4 5 6 4 4
7 3 4 3 3 3
3 2 2 1 1 2

输出 #2

text

1
21
3

说明/提示

样例 1 说明

只需要在海拔为 $9$ 的那座城市中建造蓄水厂，即可满足要求。

样例 2 说明

上图中，在 $3 $ 个粗线框出的城市中建造蓄水厂，可以满足要求。以这 $3 $ 个蓄水厂为源头在干旱区中建造的输水站分别用 $3$ 种颜色标出。当然，建造方法可能不唯一。

数据范围

本题有 10 个测试数据，每个数据的范围如下表所示：

测试数据编号	能否满足要求	$N\le$	$M\le$
1	不能	$10$	$10$
2	不能	$100$	$100$
3	不能	$500$	$500$
4	能	$1$	$10$
5	能	$10$	$10$
6	能	$100$	$20$
7	能	$100$	$50$
8	能	$100$	$100$
9	能	$200$	$200$
10	能	$500$	$500$

对于所有 10 个数据，每座城市的海拔高度都不超过 $10^6$ 。

[NOIP 2010 提高组] 引水入城

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

思路

第一步：每个蓄水厂一次 BFS

第二步：判断能不能做到

第三步：可行时，每个 SjS_jSj​ 是一段连续区间

第四步：区间覆盖贪心

样例 2 的完整推演

代码

复杂度

总结

第三步：可行时，每个 $S_j$ 是一段连续区间