记录编号	514416	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]引水入城	最终得分	100
用户昵称	梦那边的美好ET	是否通过	通过
代码语言	C++	运行时间	0.446 s
提交时间	2018-10-16 12:57:48	内存使用	1.30 MiB

#include<iostream>  
#include<cstdio>
#include<cmath> 
#include<cstring>  
#include<algorithm> 
using namespace std; 
int a[505][505],b[505][505],n,m,ans=0,f[510][510],s[510],su=0,dp[510];
struct hs{int l,r;}w[510];
inline void dfs(int x,int y){
	if(x<=0||y<=0||x>n||y>m)return;
    if(b[x][y]==1)return;
	b[x][y]=1;
	if(a[x][y]>a[x+1][y])dfs(x+1,y);
	if(a[x][y]>a[x-1][y])dfs(x-1,y);
	if(a[x][y]>a[x][y+1])dfs(x,y+1);
	if(a[x][y]>a[x][y-1])dfs(x,y-1);
	return;
}
bool hh(hs a1,hs a2){return a1.r<a2.r;}
inline int hs(){ 
    freopen("flow.in","r",stdin);        
    freopen("flow.out","w",stdout);     
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	for(int i=1;i<=m;i++){
		for(int a1=1;a1<=n;a1++)
		    for(int a2=1;a2<=m;a2++)
		        b[a1][a2]=0;
		dfs(1,i);
		for(int j=1;j<=m;j++){
			if(b[1][j]&&i!=j)s[j]=1;
			if(b[n][j])f[i][j]=1;
		}
	}
	for(int i=1;i<=m;i++){
		int ju=0;
		for(int j=1;j<=m;j++)if(f[j][i])ju=1;
		if(!ju)ans++;
	}
	if(n==1){
		int sum=0;
		for(int i=1;i<=m;i++)if(s[i]==0)sum++;
		printf("1\n");printf("%d",sum);
		return 0;
	}
	if(ans){printf("0\n");printf("%d",ans);return 0;}
	for(int i=1;i<=m;i++){
		if(s[i])continue;
		for(int j=1;j<=m;j++){
			if(f[i][j-1]==0&&f[i][j])w[++su].l=j;
			if(f[i][j]&&f[i][j+1]==0)w[su].r=j;
		}
	}
	for(int i=1;i<=m;i++)dp[i]=999999;
	sort(w+1,w+1+su,hh);int z=1;
	while(z!=su+1){
		for(int i=w[z].l-1;i<w[z].r;i++)dp[w[z].r]=min(dp[w[z].r],dp[i]+1);
		z++;
	}
	printf("1\n");printf("%d",dp[m]);
    return 0;  
}
int yy=hs();
int main(){;}