NOIP2010提高组 引水入城

【问题描述】

这道题要分几个成部分看。
第一部分（30分) 一个简单的多源BFS从第一行的点出发能到达哪些最后一行的点。
第二部分 算法1：（60分） 先用多个BFS统计出第一行每个点能到达的最后一行的点，让后枚举每个点选还是不选，最后看能否选完，输出选的最小个数。
算法2：（100分）这种算法你需要发现一个隐藏道具（悄悄告诉你吧：如果能覆盖完，那么第一行每个点所能到的最后一行的点是连续的，有图有真像：
如果像图中那样，中间有流不到的点，那么那个部分就会成为孤岛,永远无法到达。）当我们知道这个秘密过后，我们就可以用覆盖区间去做了。
注;还有一个小优化，在考虑第一行的点的时候永远只需要考虑它左右两边的点不高于它的点（自己思考吧）。
下面是满分代码（没加最后一个优化）：

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=505;
struct shu
{
int x,y;
    friend bool operator <(shu a,shu b)
    {
return a.x<b.x;
    }
}q[maxn*maxn],f[maxn];
int n,m,a[maxn][maxn];
bool vis[maxn][maxn],d[maxn][maxn]={0},b[maxn]={0};
int dx[]={0,-1,0,1};
int dy[]={1,0,-1,0};

void bfs(int p)
{
    memset(vis,0,sizeof(vis));
int root=0,frond=0;
q[root++]=(shu){1,p};
    vis[1][p]=1;
if(n==1)
    {
    d[p][p]=1;
    b[p]=1;
    }
while(root!=frond)
    {
        shu t=q[frond++];
for(int i=0;i<4;i++)
        {
int xn=t.x+dx[i],yn=t.y+dy[i];
if(xn<1||xn>n||yn<1||yn>m) continue;
if(a[xn][yn]>=a[t.x][t.y]) continue;
if(vis[xn][yn]) continue;
q[root++]=(shu){xn,yn};
            vis[xn][yn]=1;
if(xn==n)
            {
            d[p][yn]=1;
            b[yn]=1;
            }
        }
    }

}
int read()
{
int x=0;
    char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch<='9'&&ch>='0')
    {
x=x*10+ch-'0';
        ch=getchar();
    }
return x;
}

void init()
{
    n=read();
m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
    a[i][j]=read();
}
void work()
{
for(int i=1;i<=m;i++)
    {
int j;
for(j=1;j<=m;j++)
if(d[i][j])
        {
        f[i].x=j;
break;
        }
for(;j<=m;j++)
if(d[i][j]) f[i].y=j;
    }
int ans=0;
int s=1,l=m;
sort(f+1,f+1+m);
for(int i=1;i<=m;i++)
if(f[i].x<=s)
    {
int k=s;
for(int j=i;f[j].x<=s;j++)
        k=max(k,f[j].y);
        ans++;
s=k+1;
if(s>l) break;
    }
printf("%d\n",ans);
}
int main()
{
//freopen("in.txt","r",stdin);
    init();
for(int i=1;i<=m;i++)
    bfs(i);

int ans=0;
for(int i=1;i<=m;i++)
if(b[i]) ans++;
if(ans<m) printf("0\n%d",m-ans);
if(ans==m)
    {
printf("1\n");
        work();
    }
return 0;
}