Description：

$ n\times m $ 的矩形土地。每一小块都有自己的高度。水流可以由任意一块地流向周围四块地中。 给定每个小块的高度，求每个小块的积水高度。矩形外围高度为 $ 0$ 。

$1\le n,m\le300$

Solution：

发现每个点最终的高度就是它到外围的所有路径中最高点最低的路径的最高点高度，于是把每个点向他四周的点连高度为两个点中高度的较大值边权的边，求最小生成树，如果把矩形外边设为根，那么这条路径就是树上它到根的路径，于是 $dfs$ 一遍同时维护最大值即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 310

bool outside(int x,int y){return (x < 1 || y < 1 || x > n || y > m);}

int p[MAXN][MAXN];

int mx[4] = {0,0,1,-1};

int my[4] = {1,-1,0,0};

struct line{int u,v,w;};

vector<line> g;

int to(int i,int j){return (i - 1) * m + j;}

bool cmp(line a,line b){return a.w < b.w;}

struct edge

{

	int to,nxt,v;

}e[MAXN * MAXN << 1];

int edgenum = 0;

int lin[MAXN * MAXN] = {0};

void add(int a,int b,int c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].v = c;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int f[MAXN * MAXN];

int find(int x){return (f[x] == 0 ? x : f[x] = find(f[x]));}

int h[MAXN * MAXN];

bool vis[MAXN * MAXN];

void dfs(int k,int height)

{

	vis[k] = true;h[k] = height;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		dfs(e[i].to,max(height,e[i].v));

	}

	return;

}

int main()

{

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

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

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

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

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

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

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

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

			for(int k = 0;k < 4;++k)

				if(!outside(i + mx[k],j + my[k]))

					g.push_back((line){to(i,j),to(i + mx[k],j + my[k]),max(p[i][j],p[i + mx[k]][j + my[k]])});

				else

					g.push_back((line){to(i,j),n * m + 1,max(p[i][j],p[i + mx[k]][j + my[k]])});

	sort(g.begin(),g.end(),cmp);

	int cnt = n * m + 1;

	for(int i = 0;i < g.size();++i)

	{

		if(find(g[i].u) == find(g[i].v))continue;

		f[find(g[i].u)] = find(g[i].v);

		add(g[i].u,g[i].v,g[i].w);

		--cnt;

		if(cnt == 1)break;

	}

	dfs(n * m + 1,0);

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

	{

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

		{

			cout << h[to(i,j)] - p[i][j] << " ";

		}

		cout << endl;

	}

	fclose(stdin);

	fclose(stdout);

	return 0;

}