Description：

给一个矩形地图，每个位置有海拔，现在当前每个位置已经积了无穷多的水，水不能流出矩形，有些位置必须把水抽干，有些地方不用，一个抽水机可以把某个位置所有水抽干，水会向低处流，问最少需要多少个抽水机。

$1\leqslant n,m\leqslant 10^3$

Solution：

首先玩了一下发现抽水机一定放在城市里，因为如果放在其他地方可以在和他相邻的最低的城市放一个达到同样的效果，一个很显然的事情是最低的城市一定放了，因为没有别的城市能供给它，所以就联想到按高度排序，同时用一个并查集维护连通性，如果他是一个城市且联通块内还没有抽水机那就只能放一个。

但是这样有一个问题，就是海拔相同的城市可以互相到达，但是这样可能会先考虑一个不能和别的连起来的城市，加入一些地点后就可以连起来了，这时会错误的给他一个抽水机，但是它和别人连起来后不用抽水机，于是只要把所有海拔相同的城市先集中在一起处理即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 1010

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

int f[MAXN * MAXN];

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

bool g[MAXN * MAXN];

int h[MAXN * MAXN];

bool city[MAXN * MAXN];

vector< pair<int,int> > p[MAXN];

#define fi first

#define se second

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

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

int main()

{

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

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

	{

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

		{

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

			if(h[to(i,j)] < 0)

			{

				h[to(i,j)] *= -1;

				city[to(i,j)] = false;

			}

			else city[to(i,j)] = true;

			p[h[to(i,j)]].push_back(make_pair(i,j));

		}

	}

	for(int i = 1;i <= n * m;++i)f[i] = i;

	int ans = 0;

	for(int i = 0;i < MAXN;++i)

	{

		for(vector< pair<int,int> >::iterator it = p[i].begin();it != p[i].end();++it)

		{

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

			{

				int nx = it -> fi + mx[k],ny = it -> se + my[k];

				if(1 <= nx && nx <= n && 1 <= ny && ny <= m && h[to(nx,ny)] <= h[to(it -> fi,it -> se)])

				{

					int p = find(to(it -> fi,it -> se)),q = find(to(nx,ny));

					f[p] = q;g[q] |= g[p];

				}

			}

		}

		for(vector< pair<int,int> >::iterator it = p[i].begin();it != p[i].end();++it)

		{

			if(city[to(it -> fi,it -> se)] && !g[find(to(it -> fi,it -> se))])

			{

				++ans;

				g[find(to(it -> fi,it -> se))] = true;

			}

		}

	}

	cout << ans << endl;

	return 0;

}