题目

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

题目描述

一个 N×M 的城市网格，第 1 行靠湖，只能在这些城市建蓄水厂；水只能从高处流向相邻低处城市。第 N 行是干旱区，要求每座城市都能有水。若能满足，输出 1 和最少蓄水厂数；若不能，输出 0 和最后一行无法供水的城市数。

思路

要记录每个第一行的蓄水厂能够给哪些干旱区补水，所以要给每一个第一行的城市设置一个结构体Node记录每个城市能够影响到的最左和最右距离，这个时候就有问题了。如果在这一个点的影响区域是分散的呢？可以证明如果出现这种情况的话，那么干旱区的城市就一定不可能会全部有水，所以如果能够全部浇灌到的话，每个城市影响到的区域就一定是连续的，至于证明放到下面了。在记录下每个蓄水厂的可影响范围后，如果某个干旱区能被浇灌到，那么就在viss数组进行一次标记，然后如果存在没有被影响的城市的话就直接将viss数组中的所有没有被标记下来的点的数量给记录下来，最后输出 0 和没有被浇灌的干旱区的数量即可。如果全部被标记了的话就去暴力的找最少要多少个蓄水厂即可。

为什么，如果能够将干旱区全部浇灌到的话每个点就一定是连续的呢？

这里使用反证法：

假设某个蓄水厂 A 能到达最后一行第 l 列和第 r 列，但不能到达中间的 k 列（l<k<r）。

从 A 到 l 和从 A 到 r 的两条水流路径，会把中间的 k 列夹在中间，像两堵墙一样。

因为最后一行全部都要被供水，所以 k 列一定由另一个蓄水厂 B 来供水。B 到 k 的水流路径必须穿过这两堵墙之一，设交点为 X。

那么水可以这样走：
A 先沿着自己的路径流到 X，再从 X 沿着 B 的路径流到 k。
两段都是从高到低，所以 A 也能到达 k。

这就与“A 不能到达 k ”矛盾。

所以，如果最后一行全部能被供水，那么每个蓄水厂能到达的最后一行城市一定是连续的一段，不会出现中间漏掉的情况。

AC代码：O（n*m2）

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int n, m;
vector<vector<int>> mp;
//用于记录干旱区的某个点是否能被访问
vector<bool> viss;

//记录某个蓄水厂能够影响到的区域的最左和最右边
struct Node {
    int l = INT_MAX;
    int r = 0;
    Node(int _l, int _r) :l(_l), r(_r) {}
    Node() {}
};

//防止数组越界
bool pd(int x, int y) {
    if (x < 1) return false;
    if (x > n) return false;
    if (y < 1) return false;
    if (y > m) return false;
    return true;
}

//dfs搜寻每个点
Node dfs(int x,int y, Node& node, vector<vector<bool>>& vis) {
    if (vis[x][y]) return node;
    vis[x][y] = true;
    if (x == n) {
        node.l = min(node.l, y);
        node.r = max(node.r, y);
        viss[y] = true;
        vis[x][y] = true;
    }
    if (pd(x + 1, y) && mp[x][y] > mp[x + 1][y]) dfs(x + 1, y, node, vis);
    if (pd(x, y + 1) && mp[x][y] > mp[x][y + 1]) dfs(x, y + 1, node, vis);
    if (pd(x - 1, y) && mp[x][y] > mp[x - 1][y]) dfs(x - 1, y, node, vis);
    if (pd(x, y - 1) && mp[x][y] > mp[x][y - 1]) dfs(x, y - 1, node, vis);
    return node;
}

void solve() {
    cin >> n >> m;
    mp.assign(n + 1, vector<int>(m + 1));
    viss.assign(m + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> mp[i][j];
        }
    }
    vector<Node> dp(m + 1);
    for (int i = 1; i <= m; i++) {
        vector<vector<bool>> vis(n + 1, vector<bool>(m + 1));
        Node node;
        dp[i] = dfs(1, i, node, vis);
    }
    int cnt = 0;
    for (int i = 1; i <= m; i++) {
        //如果出现某个点没有被灌溉到直接跑这个逻辑
        if (!viss[i]) {
            cout << 0 << endl;
            for (; i <= m; i++) {
                if(!viss[i]) cnt++;
            }
            cout << cnt << endl;
            return;
        }
    }
    int l = 1, r = 0;
    //暴力找最少需要多少蓄水厂
    while (r < m) {
        for (int i = 1; i <= m; i++) {
            if (l >= dp[i].l) {
                r = max(r, dp[i].r);
            }
        }
        l = r + 1;
        cnt++;
    }
    cout << 1 << endl;
    cout << cnt << endl;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    //cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}