Luogu p1514 [noip2010 improvement group] water diversion into the city

Luogu P1514 [NOIP2010 Improvement group ] Water into the city Answer key

Topic link ：P1514 [NOIP2010 Improvement group ] Water into the city

The question ：

In a distant country , On one side is a beautiful lake , On the other side is the boundless desert . The administrative division of the country is very special , It just makes up a $N$ That's ok $\times M$ Column rectangle , As shown in the figure above , Each grid represents a city , Every city has an altitude .

In order to make the residents drink the clear lake water as much as possible , Now we need to build water conservancy facilities in some cities . There are two kinds of water conservancy facilities , They are water storage plant and water delivery station . The function of the water storage plant is to pump water from the lake to the reservoir of the city .

therefore , There's only the second one adjacent to the lake $1$ Yes, cities can build water storage plants . The function of the water delivery station is to use the height drop through the water delivery pipeline , Transport water from high to low . Therefore, the premise for a city to build a water conveyance station , It's an adjacent city with a higher altitude and a public edge , Water conservancy facilities have been built . Due to the first $N$ The city is near the desert , It's the arid part of the country , So every city is required to have water conservancy facilities . that , Can this requirement be met ？ If you can , Please calculate the minimum number of water storage plants to be built ; If not , Find out the number of cities in arid areas that can't have water conservancy facilities .

First of all, we can think of running directly at each shore point dfs

At the same time, record the number of cities that each point can cover

What are the characteristics of a city that can be covered by one point

If there is any solution , So what any water storage plant can cover is the line segment

This is not easy to think of , But it's easy to prove

Here's a mouthful of proof

Consider counter evidence

Set up a water storage plant $u$ The leftmost and rightmost cities that can be covered are $l,r$

be $u,l,r$ The three points must form a closed figure similar to a triangle

Obviously, if other water storage plants are to be covered $[l,r]$ In the point , It must pass through one of the sides of the triangle

If a point $x\in [l,r]$ It cannot be covered by water flowing from any point in the triangle

Then, no matter where the water from the outside flows through the triangle , Can not flow to $x$ , Then there is no solution

Therefore, when there is a solution, any city that can be covered by the water storage plant forms a line segment

Know the line segment , How to calculate the answer ？

We can set up a $L$ Indicates the location of the city currently covered （ Cover from left to right ）

And the left endpoint of any line segment $l_i\le L$ Can make $L$ Move right to $r_i$

So we greedily choose all the satisfaction $l_i\le L$ The largest of the line segments of $r_i$ , To update $L$

And then it's gone

Time complexity $O(nm)$

Code ：

#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;
}

Reprint please explain the source