【寒假作业】【NOIP2010】引水入城

果然任何最后一题都是鬼畜树/图的题

可以发现第一排每个点能到的点是一段区间。。

于是几遍BFS就完了

第一遍从第一排BFS，判断有没有不可能的

第二遍从最后一排，从左往右BFS，找出第一排能到达的最后一排的最左端点

第三遍从最后一排，从右往左BFS，找出第一排能到达的最后一排的最右端点

最后排个序贪心下就行了

【写起来也是有够麻烦的

// <flow.cpp> - 02/14/16 15:45:23
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
const int MAXN=502;
int n,m;
int h[MAXN][MAXN];
int vis[MAXN][MAXN];
int dp[MAXN][2];
queue <pair<int,int> > q;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
bool check(int x,int y){return x>=1&&x<=n&&y>=1&&y<=m;}
void bfs(bool f,int k){
	q.push(make_pair(f?n:1,k));
	while(!q.empty()){
		int x=q.front().first,y=q.front().second;q.pop();
		for(int i=0;i<4;i++){
			int xx=x+dx[i],yy=y+dy[i];
			if(!check(xx,yy)||vis[xx][yy])continue;
			if(!f&&h[x][y]<=h[xx][yy])continue;
			if(f&&h[x][y]>=h[xx][yy])continue;
			vis[xx][yy]=k;
			q.push(make_pair(xx,yy));
		}
	}
}
void clear(){for(int i=1;i<=n;i++)for(int o=1;o<=m;o++)vis[i][o]=0;}
struct C{int l,r;}c[MAXN];
bool cmp(C a,C b){return a.l==b.l?a.r<b.r:a.l<b.l;}
int main(){
	freopen("flow.in","r",stdin);
	freopen("flow.out","w",stdout);
	n=getint(),m=getint();
	for(int i=1;i<=n;i++)
		for(int o=1;o<=m;o++)
			h[i][o]=getint();
	for(int i=1;i<=m;i++)if(!vis[1][i]){vis[1][i]=i;bfs(0,i);}
	int no=0;
	for(int i=1;i<=m;i++)if(!vis[n][i])no++;
	if(no){printf("0\n%d",no);return 0;}
	clear();for(int i=1;i<=m;i++)if(!vis[n][i]){vis[n][i]=i;bfs(1,i);}
	for(int i=1;i<=m;i++)c[i].l=vis[1][i];
	clear();for(int i=m;i>=1;i--)if(!vis[n][i]){vis[n][i]=i;bfs(1,i);}
	for(int i=1;i<=m;i++)c[i].r=vis[1][i];
	for(int i=1;i<=m;i++){if(!c[i].l)c[i].l=c[i].r;if(!c[i].r)c[i].r=c[i].l;}
	sort(c+1,c+1+m,cmp);
	int now=0,to=0,tot=0;
	for(int i=1;i<=m;i++){
		if(now+1>=c[i].l)to=max(to,c[i].r);
		else now=to,to=max(to,c[i].r),tot++;
	}
	if(now!=m)tot++;
	printf("1\n%d",tot);
	return 0;
}

// <flow.cpp> - 02/14/16 15:45:23

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=502;

int n,m;

int h[MAXN][MAXN];

int vis[MAXN][MAXN];

int dp[MAXN][2];

queue <pair<int,int> > q;

const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

bool check(int x,int y){return x>=1&&x<=n&&y>=1&&y<=m;}

void bfs(bool f,int k){

q.push(make_pair(f?n:1,k));

while(!q.empty()){

int x=q.front().first,y=q.front().second;q.pop();

for(int i=0;i<4;i++){

int xx=x+dx[i],yy=y+dy[i];

if(!check(xx,yy)||vis[xx][yy])continue;

if(!f&&h[x][y]<=h[xx][yy])continue;

if(f&&h[x][y]>=h[xx][yy])continue;

vis[xx][yy]=k;

q.push(make_pair(xx,yy));

}

void clear(){for(int i=1;i<=n;i++)for(int o=1;o<=m;o++)vis[i][o]=0;}

struct C{int l,r;}c[MAXN];

bool cmp(C a,C b){return a.l==b.l?a.r<b.r:a.l<b.l;}

int main(){

freopen("flow.in","r",stdin);

freopen("flow.out","w",stdout);

n=getint(),m=getint();

for(int i=1;i<=n;i++)

for(int o=1;o<=m;o++)

h[i][o]=getint();

for(int i=1;i<=m;i++)if(!vis[1][i]){vis[1][i]=i;bfs(0,i);}

int no=0;

for(int i=1;i<=m;i++)if(!vis[n][i])no++;

if(no){printf("0\n%d",no);return 0;}

clear();for(int i=1;i<=m;i++)if(!vis[n][i]){vis[n][i]=i;bfs(1,i);}

for(int i=1;i<=m;i++)c[i].l=vis[1][i];

clear();for(int i=m;i>=1;i--)if(!vis[n][i]){vis[n][i]=i;bfs(1,i);}

for(int i=1;i<=m;i++)c[i].r=vis[1][i];

for(int i=1;i<=m;i++){if(!c[i].l)c[i].l=c[i].r;if(!c[i].r)c[i].r=c[i].l;}

sort(c+1,c+1+m,cmp);

int now=0,to=0,tot=0;

for(int i=1;i<=m;i++){

if(now+1>=c[i].l)to=max(to,c[i].r);

else now=to,to=max(to,c[i].r),tot++;

}

if(now!=m)tot++;

printf("1\n%d",tot);

return 0;

}