洛谷P1514 [NOIP2010 提高组] 引水入城 题解

题目链接：P1514 [NOIP2010 提高组] 引水入城

题意：

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

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

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

首先可以想到我们直接在每个岸边的点跑dfs

同时记录每个点能覆盖的城市数目

那么一个点能覆盖的城市有什么特点呢

如果有解，那么任意蓄水厂能覆盖的都是线段

这个不容易想到，但是很容易证明

这里是一个口糊证明

考虑反证法

设一个蓄水厂 $u$ 能覆盖的最左和最右城市分别为 $l,r$

则 $u,l,r$ 三点一定构成一个类似于三角形的封闭图形

显然其他蓄水厂如果要覆盖 $[l,r]$ 中的点，一定会经过三角形的某条边

如果某个点 $x \in [l,r]$ 不能被这个三角形内任意一点流出的水覆盖

则外界流入的水无论从哪里经过三角形，都无法流到 $x$ ，那么就无解了

因此有解的时候任意蓄水厂能覆盖的城市构成一条线段

知道了线段，怎么算答案呢？

我们可以设一个 $L$ 表示目前覆盖到的城市位置（从左向右覆盖）

而任意一条线段的左端点 $l_i\le L$ 均可以使 $L$ 右移至 $r_i$

于是我们贪心地选择所有满足 $l_i\le L$ 的线段中最大的 $r_i$ ，去更新 $L$

然后就没了

时间复杂度 $O(nm)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e3+15)

int n,m;
int dx[5]={0,0,1,-1};
int dy[5]={1,-1,0,0};
int vis[N][N],h[N][N],l[N][N],r[N][N];
bool safe(int x,int y)
{return 1<=x&&x<=n&&1<=y&&y<=m;}
void dfs(int x,int y)
{
    vis[x][y]=1;
    for(int i=0; i<4; i++)
    {
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(!safe(tx,ty)||h[tx][ty]>=h[x][y])continue;
        if(!vis[tx][ty])dfs(tx,ty);
        l[x][y]=min(l[x][y],l[tx][ty]);
        r[x][y]=max(r[x][y],r[tx][ty]);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    memset(l,0x3f,sizeof(l));
    cin >> n >> m;
    for(int i=1; i<=m; i++)
        l[n][i]=r[n][i]=i;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin >> h[i][j];
    for(int i=1; i<=m; i++)
        if(!vis[1][i])dfs(1,i);
    bool ok=1;int res=0;
    for(int i=1; i<=m; i++)
        if(!vis[n][i]) { ok=0;++res; }
    if(!ok)
    {
        cout << "0\n" << res << '\n';
        return 0;
    }
    int L=1,R=r[1][1];
    while(L<=m)
    {
        for(int i=1; i<=m; i++)
            if(l[1][i]<=L)
                R=max(R,r[1][i]);
        L=R+1; ++res;
    }
    cout << "1\n" << res << '\n';
    return 0;
}