【Codeforces 659F】Polycarp and Hay

  把点从大到小排序，然后并查集维护连通块大小，检查是否有解。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=1010,maxv=1000010;

struct Node {int x,y,h;}P[maxv];
bool cmp (const Node &a,const Node &b) {return a.h<b.h;}

int fa[maxv],c[maxv];
int map[maxn][maxn];
int ans[maxn][maxn];
LL k;
int n,m,cnt;

int p(int x,int y) {return (x-1)*m+y;}
int Find(int x) {return x==fa[x]?x:fa[x]=Find(fa[x]);}

void DFS(int h,int v,int x,int y)
{
	ans[x][y]=h;cnt--;
	if (!cnt) return;
	if (x>1 && Find(p(x-1,y))==v && !ans[x-1][y]) DFS(h,v,x-1,y);
	if (!cnt) return;
	if (x<n && Find(p(x+1,y))==v && !ans[x+1][y]) DFS(h,v,x+1,y);
	if (!cnt) return;
	if (y>1 && Find(p(x,y-1))==v && !ans[x][y-1]) DFS(h,v,x,y-1);
	if (!cnt) return;
	if (y<m && Find(p(x,y+1))==v && !ans[x][y+1]) DFS(h,v,x,y+1);
}

int main()
{
	scanf("%d%d%I64d",&n,&m,&k);
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
	{
		scanf("%d",&map[i][j]);
		int v=p(i,j);
		P[v].x=i;P[v].y=j;
		P[v].h=map[i][j];
		fa[v]=v;c[v]=1;
	}
	sort(P+1,P+1+n*m,cmp);
	for (int i=n*m;i;i--)
	{
		int x=P[i].x,y=P[i].y,h=P[i].h,v=p(x,y);
		if (x>1 && map[x-1][y]>=map[x][y] && Find(v)!=Find(p(x-1,y))) c[Find(v)]+=c[Find(p(x-1,y))],fa[Find(p(x-1,y))]=Find(v);
		if (y>1 && map[x][y-1]>=map[x][y] && Find(v)!=Find(p(x,y-1))) c[Find(v)]+=c[Find(p(x,y-1))],fa[Find(p(x,y-1))]=Find(v);
		if (x<n && map[x+1][y]>=map[x][y] && Find(v)!=Find(p(x+1,y))) c[Find(v)]+=c[Find(p(x+1,y))],fa[Find(p(x+1,y))]=Find(v);
		if (y<m && map[x][y+1]>=map[x][y] && Find(v)!=Find(p(x,y+1))) c[Find(v)]+=c[Find(p(x,y+1))],fa[Find(p(x,y+1))]=Find(v);
		if (k%h==0 && k/h<=c[Find(v)])
		{
			puts("YES");
			cnt=k/h;
			DFS(h,Find(v),x,y);
			for (x=1;x<=n;x++)
			{
				for (y=1;y<m;y++)
					printf("%d ",ans[x][y]);
				printf("%d\n",ans[x][m]);
			}
			return 0;
		}
	}
	puts("NO");
	return 0;
}