[NOIp2010] luogu P1514 引水入城

跟 zzy, hwx 等人纠结是否回去上蛋疼的董老板的课。

题目描述

如图所示。你有一个 N×MN\times MN×M 的矩阵，水可以从一格流到与它相邻的格子，需要满足起点的海拔严格高于终点海拔。定义两个格子相邻，当且仅当它们合法存在，且它们的横坐标和纵坐标中有且仅有一个相同，另一个数值之差严格为 111。请你告诉我，至少需要在第一行的多少格上放水，才能使最后一行的所有格子都有水。

Solution

这算是我想到的一个贪心吧。从左往右处理最后一行的每个点，找到选中后水能流到这个点的、第一行的最右边的点，并打通这个点。标记所有被该点浇灌的格子。

证明： 当处理到第 yyy 格的时候，前 y−1y-1y−1 格早已被处理完毕。所以如果在第一行存在两个点，它们都能浇到 yyy，选右边的点显然更有意义，因为它貌似有潜力浇灌更多的点。

时间复杂度 O(N3)O(N^3)O(N3)。

#include<cstdio>

#include<cstdlib>

#include<cstring>

const int MAXN=510;

int n,m;

int fx[6]={0,0,1,-1};

int fy[6]={1,-1,0,0};

bool vis[MAXN][MAXN];

struct node{

	int x,y;

}q[MAXN*MAXN*10];

int st,ed;

int a[MAXN][MAXN];

int tf[MAXN];

void SPFA(int stx,int sty,int type){

	st=1;ed=2;

	q[st].x=stx;q[st].y=sty;

	memset(vis,0,sizeof(vis));vis[stx][sty]=1;

	while(st!=ed){

		node x=q[st];

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

			int nx=x.x+fx[i],ny=x.y+fy[i];

			if(nx<1||nx>n||ny<1||ny>m) continue;

			if(vis[nx][ny]||(type?(a[nx][ny]<=a[x.x][x.y]):(a[nx][ny]>=a[x.x][x.y]))) continue;

			vis[nx][ny]=1;

			q[ed].x=nx;q[ed++].y=ny;

		}

		++st;

	}

}

int work(int ST){

	SPFA(n,ST,1);

	ST=0;

	for(int i=m;i>=1;--i)

		if(vis[1][i]){

			ST=i;

			break;

		}

	if(!ST) return 0;

	SPFA(1,ST,0);

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

		if(vis[n][i])

			tf[i]=1;

	return 1;

}

int main(){

	scanf("%d%d",&n,&m);

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

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

			scanf("%d",&a[i][j]);

	memset(tf,0,sizeof(tf));

	int cnt=0,ans=0;

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

		if(tf[i]) continue;

		int r=work(i);

		if(!r)

			++cnt;

		else

			++ans;

	}

	if(cnt)

		printf("0\n%d",cnt);

	else

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

}