题目相关

题目链接: 洛谷 P1514 引水入城

题目描述

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

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

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

输入格式

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

输出格式

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

数据范围

$N\le 500, M\le 500$，每座城市的海拔高度都不超过 $10^6$。

题目解析

判断是否能满足要求

为了尽可能满足要求，可以在第 $1$ 行所有城市都建蓄水厂。

对于每个蓄水厂，BFS 便可以得到其能覆盖到的格子。对所有的第 $1$ 行城市 BFS 后，统计一下最后一行没有被访问过的城市数即可。

如果存在未被访问的，则不能满足要求，同时没访问的城市数也即不能满足的城市数。

满足条件，最小修建蓄水厂数

有这样一个结论：在有解的前提下，每一个蓄水厂可覆盖的最后一行的城市必定是一个连续的区间。

证明：考虑某一个蓄水厂覆盖的第 $N$ 行的区间存在中断点，因为有解，则必定有其他蓄水厂覆盖了这些中断点。

设该蓄水厂能覆盖的所有区域（不只是第 $N$ 行）为 $A$，中断点的区域为 $B$，那么任何从 $A$ 出发的点都无法到达 $B$，更进一步说，任何经过 $A$ 的路径都无法到达 $B$。

而对于其他蓄水厂，如果要到达 $B$，其路径必定经过 $A$ 中区域，无法到达 $B$，与假设不符。

所以某个蓄水厂覆盖的第 $N$ 行的城市必定是一个连续区间。

所以在计算覆盖范围时，可以顺便统计每一个蓄水厂的覆盖区间。那么最终问题就转化为用最少的线段覆盖所有区间，经典的线段覆盖问题。

代码

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
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 510, maxm = 510;
const int dx[4] = { -1, 0, 1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

int n, m;
int h[maxn][maxm];
int vis[maxn][maxm];
int vis_last[maxm];
pair<int, int> seg[maxm];

void bfs(const pair<int, int> &s) {
    // initilize
    memset(vis, 0, sizeof(vis));
    queue<pair<int, int> > q;
    q.push(s);
    vis[s.first][s.second] = 1;

    // bfs
    while (!q.empty()) {
        pair<int, int> u = q.front();
        q.pop(); 
        for (int d = 0; d < 4; ++d) {
            pair<int, int> v = make_pair(u.first + dx[d], u.second + dy[d]);
            if (v.first <= 0 || v.first > n || v.second <= 0 || v.second > m) continue;
            if (vis[v.first][v.second]) continue;
            if (h[v.first][v.second] >= h[u.first][u.second]) continue;
            q.push(v);
            vis[v.first][v.second] = 1;
        }
    }

    // update city cover info
    for (int j = 1; j <= m; ++j) {
        vis_last[j] |= vis[n][j];
    }

    // update segment info
    seg[s.second].first = 1;
    while (seg[s.second].first <= m && !vis[n][seg[s.second].first]) ++seg[s.second].first;
    seg[s.second].second = m;
    while (seg[s.second].second >= 1 && !vis[n][seg[s.second].second]) --seg[s.second].second;
}

int main() {
    // read input
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            scanf("%d", &h[i][j]);
        }
    }

    // find uncovered cities
    int uncovered_num = 0;
    for (int j = 1; j <= m; ++j) {
        bfs(make_pair(1, j));
    }
    for (int j = 1; j <= m; ++j) {
        if (!vis_last[j]) {
            ++uncovered_num;
        }
    }
    if (uncovered_num) {
        printf("%d\n%d", 0, uncovered_num);
        exit(0);
    }

    // calculate min cover
    sort(seg + 1, seg + 1 + m);
    int construct_num = 0;
    int current_cover_max = 0;
    int next_cover_max = seg[1].second;
    for (int i = 1; i <= m; ++i) {
        if (seg[i].first > m) break;
        if (seg[i].first > current_cover_max + 1) {
            construct_num += 1;
            current_cover_max = next_cover_max;
        }
        next_cover_max = max(next_cover_max, seg[i].second);
    }
    if (current_cover_max < m) 
        ++construct_num;
    printf("%d\n%d", 1, construct_num);

    return 0;
}