【洛谷 P1514】引水入城 I 广搜 + 区间覆盖

约定不等于承诺〃 2023-06-03 15:54 64阅读 0赞

**[https://www.luogu.org/problem/P1514][https_www.luogu.org_problem_P1514]**

**NOIP **

在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政 区划十分特殊，刚好构成一个N行M列的矩形，如上图所示，其中每个格子都代表一座城 市，每座城市都有一个海拔高度。 为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施 有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的 蓄水池中。因此，只有与湖泊毗邻的第1行的城市可以建造蓄水厂。而输水站的功能则是通 过输水管线利用高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前提，是 存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。 由于第N行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利 设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干 旱区中不可能建有水利设施的城市数目。

![891812-20190905155921364-319234810.png][]

n=5,m=9

输入描述 Input Description

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

输出描述 Output Description

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

**样例输入**

Sample Input

2 5

9 1 5 4 3

8 7 6 1 2

**样例输出**

Sample Output

**数据范围及提示**

「数据范围」 本题共有10个测试数据

1 <=N <= 500,  1 <= M <= 500

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

自上而下引水,可以得到最后一行的点是否被覆盖,如果不行就提前结束;

自下而上反向引水可以得到第一行每个点能够覆盖的区间,分两次广搜,避免覆盖;

广搜后得到的区间要做最少区间覆盖的计算。

#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cstdlib>
    #include<vector>
    #include<cmath>
    #include<algorithm>
    #include<queue>
    #define mod 1000000007
    using namespace std;
    bool vis[505][505];
    
    struct node {
        int a, b;
        node(int x, int y):a(x), b(y) {}
    };
    bool operator<(const node& a, const node& b)
    {
        return a.a == b.a ? a.b < b.b : a.a < b.a;
    }
    void bfs(vector<vector<int> >& G, vector<vector<int> >& b,
        int x, int y, int v, int f)
    {
        queue<node> q;
        q.push({x, y});
        b[x][y] = v;
        vis[x][y] = true;
        int dx[4] = {-1, 1, 0, 0};
        int dy[4] = {
         0, 0, 1, -1};
        int nx, ny;
        int n = G.size();
        int m = G[0].size();
        while (!q.empty()) {
            node head = q.front();
            q.pop();
            x = head.a, y = head.b;
            for (int k = 0; k < 4; k++) {
                nx = x + dx[k];
                ny = y + dy[k];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny])
                    continue;
                if (f == 0 && G[nx][ny] >= G[x][y]) continue;
                if (f == 1 && G[nx][ny] <= G[x][y]) continue;
                b[nx][ny] = b[x][y];
                vis[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
    
    ////the personal solution ////
    int main() {
        int n, m;
        while (cin >> n >> m) {
            vector<vector<int> > G(n);
            vector<vector<int> > b(n, vector<int>(m, -1));
            vector<vector<int> > r(n, vector<int>(m, -1));
            for (int i = 0; i < n; i++) {
                G[i].resize(m);
                for (int j = 0; j < m; j++) {
                    cin >> G[i][j];
                }
            }
            // from top to bottom to bfs and search the city
            memset(vis, 0, sizeof(vis));
            for (int i = 0; i < m; i++) {
                bfs(G, b, 0, i, 0, 0);
            }
            int cnt = 0;
            //count the satisfied number of cities in the nth row
            for (int i = 0; i < m; i++) {
                if (b[n - 1][i] >= 0) {
                    cnt++;
                }
            }
            if (cnt != m) {
                printf("0\n%d\n", m - cnt);
                continue;
            }
            memset(vis, 0, sizeof(vis));
            //reverse flood to record the max segment of each point in row 0
            for (int i = 0; i < m; i++) {
                if (!vis[n - 1][i]) bfs(G, b, n - 1, i, i, 1);
            }
            memset(vis, 0, sizeof(vis));
            for (int i = m - 1; i >= 0; i--) {
                if (!vis[n - 1][i]) bfs(G, r, n - 1, i, i, 1);
            }
            vector<struct node> vec;
            for (int i = 0; i < m; i++) {
                if (b[0][i] < 0) b[0][i] = r[0][i];
                if (r[0][i] < 0) r[0][i] = b[0][i];
                vec.push_back({b[0][i], r[0][i]}); // b[0][i] == r[0][i] = -1 will not happen cause it is satisfied in this step
            }
            // segment coverage
            sort(vec.begin(), vec.end());
            int cur = -1, nx = 0, to = 0;
            cnt = 0;
            for (int i = 0; i < m; i++) {
                if (cur + 1 >= vec[i].a) {
                    to = vec[i].b;
                } else {
                    cur = to, to = vec[i].b, cnt++;
                }
            }
            if (cnt != m) {
                cnt++;
            }
            printf("1\n%d\n", cnt);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/wangzming/p/11466611.html

[https_www.luogu.org_problem_P1514]: https://www.luogu.org/problem/P1514
[891812-20190905155921364-319234810.png]: /images/20230601/ddb3718164b44bf1b957aa5beaa45f80.png