P1514 引水入城

admin

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



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

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

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

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

输入输出样例
输入样例#1：
2 5
9 1 5 4 3
8 7 6 1 2
输出样例#1：
1
1
输入样例#2：
3 6
8 4 5 6 4 4
7 3 4 3 3 3
3 2 2 1 1 2
输出样例#2：
1
3
说明
【样例1 说明】

只需要在海拔为9的那座城市中建造蓄水厂，即可满足要求。

【样例2 说明】



上图中，在3 个粗线框出的城市中建造蓄水厂，可以满足要求。以这3个蓄水厂为源头在干旱区中建造的输水站分别用3 种颜色标出。当然，建造方法可能不唯一。

秀木于林

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. int dx[]={-1,0,1,0};
   
4. int dy[]={0,1,0,-1};
   
5. int mp[510][510],f[520],vis[510][510],ans,l[510][510],r[510][510],n,m;
   
6. bool flag=1;
   
7. void dfs(int x,int y)
   
8. {
   
9.    vis[x][y]=1;
   
10.    for(int i=0;i<4;i++)
    
11.    {
    
12.        int x1=x+dx[i];
    
13.        int y1=y+dy[i];
    
14.        if(x1<1 || x1>n || y1<1 || y1>m || mp[x][y]<=mp[x1][y1]) continue;
    
15.        if(!vis[x1][y1]) dfs(x1,y1);
    
16.        l[x][y]=min(l[x][y], l[x1][y1]);
    
17.        r[x][y]=max(r[x][y], r[x1][y1]);
    
18.    }
    
19. 
    
20. }
    
21. int main()
    
22. {
    
23.     memset(l, 21000000, sizeof(l));
    
24.     cin>>n>>m;
    
25.     for(int i=1;i<=n;i++)
    
26.         for(int j=1;j<=m;j++)
    
27.         {cin>>mp[i][j];if (i==n) l[i][j]=r[i][j]=j;}
    
28.     for(int i=1;i<=m;i++)
    
29.         if(!vis[1][i])dfs(1,i);
    
30.         for(int i=1;i<=m;i++)if(!vis[n][i]) {flag=0;ans++;}
    
31.         if(!flag) {cout<<0<<endl<<ans<<endl;return 0;}
    
32.         f[1]=1;
    
33.     int left=1,right=r[1][1];
    
34.      while (left<=m)
    
35.     {
    
36.         for(int i=1;i<=m;i++)
    
37.         if (l[1][i]<=left)right=max(right, r[1][i]);
    
38.         left=right+1;
    
39.         ans++;
    
40.     }
    
41.     cout<<1<<endl<<ans<<endl;
    
42.     return 0;
    
43. }
    

复制代码

loris

#include<bits/stdc++.h>
using namespace std;
const int mm=501;
int n,m;
int l[mm],r[mm];
int mp[mm][mm];
bool bb[mm];
struct BFS
{
    int x,y;
}bfs[1000000];
int dr1[5]={0,0,0,1,-1};
int dr2[5]={0,1,-1,0,0};
bool check(int x,int y)
{
    if(x>=1&&x<=n&&y>=1&&y<=m)
        return 1;
    else
        return 0;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>mp[j];

    ///BFS(找每个沿湖城市可覆盖的区间)
    int k=1;
    for(int i=1;i<=m;i++)
    {
        //cout<<i<<endl;
        int a=1,b=2;
        bool bo=0;
        int ll=520,rr=0;
        bfs[a].x=1;bfs[a].y=i;
        while(a<b)
        {
            int xx,yy;
            for(int j=1;j<=4;j++)
            {
                xx=bfs[a].x+dr1[j];
                yy=bfs[a].y+dr2[j];
                if(check(xx,yy)&&mp[bfs[a].x][bfs[a].y]>mp[xx][yy])
                {
                    bfs.x=xx;
                    bfs.y=yy;
                    b++;
                    if(xx==n)
                    {
                        bb[yy]=1;
                        if(yy>rr)
                        {
                            rr=yy;
                            bo=1;
                        }
                        if(yy<ll)
                        {
                            ll=yy;
                            bo=1;
                        }
                    }
                }
            }
            a++;
        }
        if(bo)
        {
            l[k]=ll;
            r[k]=rr;
            k++;
        }
    }
    k--;

    ///CHECK
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        if(bb==0)
        {
            ans++;
        }
    }
    if(ans>0)
    {
        cout<<0<<endl<<ans;
        return 0;
    }
    cout<<1<<endl;
    /*
    for(int i=1;i<=k;i++)
    {
        cout<<l<<' '<<r<<endl;
    }
    */

    ///DP
    int f[mm];
    f[1]=0;
    for(int i=2;i<=mm-1;i++)
        f=mm;
    for(int i=1;i<=k;i++)
    {
        int _min=mm;
        for(int j=l;j<r;j++)
        {
            if(f[j]<_min)
                _min=f[j];
        }
        if(l==1)
            f[r]=_min+1;
        else
            f[r]=min(f[r],_min+1);
    }
    cout<<f[m];

    return 0;
}
/*
3 5
9 1 5 4 3
8 4 3 3 4
2 3 5 4 3
*/