Description

摘自洛谷题面。

你有一张 $m \times n$ 的地图，地图上所有点都被洪水淹没了。你知道地图上每个网格的海拔高度，其中一部分点属于 Byteburg 城。你需要放置尽可能少的巨型抽水机，将 Byteburg 城从洪水中解救出来。巨型抽水机会抽干该格子的所有水，直到该格子不被洪水淹没为止。

水会在有公共边的格子间从高向低流动。

Solution

首先我们可以发现，在相邻的格子中，放在海拔低的地方一定会比放在海拔高的地方更优，不管两个地方是不是城区，因为放在海拔低的地方一定可以抽干海拔高的地方可以抽干的地方，所以我们先把所有坐标按照海拔从低到高排序，然后依次考虑。

考虑到这其实是一个连通性问题，所以我们使用并查集维护。

把所有海拔相同的坐标放在一起考虑，假设现在取出了一个坐标 $(x,y)$，那么将与 $(x,y)$ 相邻且海拔不高于 $(x,y)$ 的位置并入同一个并查集。

然后检查是否需要放抽水机，由于我们从低到高考虑位置，所以现在如果在一个并查集中的海拔最低的位置放一个抽水机，那么一定可以抽完并查集内的水，所以当这个位置是城区，并且这个并查集中还没有放抽水机，那么就放一个抽水机即可。

注意，一定要将所有海拔相同的坐标都并入并查集之后再检查是否需要放抽水机！

Code

/*by qwer6*/
/*略去缺省源和快读快写*/
const int N=1005,dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int n,m,ans;
int h[N][N];
vector<pii>a[N];
struct DSU{
	int n,m;
	int fa[N*N],siz[N*N];
	void init(int _n){
		n=_n;
		for(int i=1;i<=n;i++)
			fa[i]=i,siz[i]=0;
	}
	int find(int x){
		if(fa[x]==x)return x;
		return fa[x]=find(fa[x]);
	}
	void merge(int x,int y){
		x=find(x),y=find(y);
		if(x==y)return ;
		fa[x]=y;
		siz[y]+=siz[x];
	}
}dsu;
signed main(){
	read(m),read(n);
	dsu.init(n*m);
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++){
			read(h[i][j]);
			a[abs(h[i][j])].push_back({i,j});
		}
	for(int i=1,x,y,xx,yy,fa;i<=1000;i++){
		for(pii tmp:a[i]){
			x=tmp.first,y=tmp.second;
			for(int j=0;j<4;j++){
				xx=x+dx[j],yy=y+dy[j];
				if(xx<1||xx>m)continue;
				if(yy<1||yy>n)continue;
				if(abs(h[x][y])<abs(h[xx][yy]))continue;
				dsu.merge(id(x,y),id(xx,yy));
			}
		}
		for(pii tmp:a[i]){
			x=tmp.first,y=tmp.second;
			fa=dsu.find(id(x,y));
			if(h[x][y]>0&&dsu.siz[fa]==0){
				ans++;
				dsu.siz[fa]=1;
			}
		}
	}
	write(ans);
}

bfs是需要优化的，具体看我进队的处理

#include<bits/stdc++.h>
#pragma GCC optimize ("Ofast")
using namespace std;
const int N=1100;
inline int read() {
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int n, m, ans, tsp, res, mp[N][N], now[N][N]; bool v[N][N];
int dx[4]={1, -1, 0, 0};
int dy[4]={0, 0, -1, 1};
struct node {int x, y, c;} a[N*N]; int len;
bool cmp(node a, node b) {return a.c<b.c;}
void bfs(int sx, int sy) {
	deque<node> q; q.push_back({sx, sy}); ans++;
	v[sx][sy]=True; now[sx][sy]=mp[sx][sy];
	while(q.size()) {
		auto t=q.front(); q.pop_front();
		for(int i=0;i<4;i++) {
			int xx=t.x+dx[i], yy=t.y+dy[i];
			if(xx<=0||yy<=0||xx>m||yy>n) continue;
			if(mp[xx][yy]>0&&now[t.x][t.y]>mp[xx][yy]) continue;
			int h=max(now[t.x][t.y], abs(mp[xx][yy]));
			if(h<now[xx][yy]) {
				now[xx][yy]=h;
				if(!v[xx][yy]) {
					v[xx][yy]=True; 
					if(q.size()&&now[xx][yy]<=now[q.front().x][q.front().y]) q.push_front({xx, yy});
					else q.push_back({xx, yy});
				}
			}
		}
		v[t.x][t.y]=False;
	}
}
int main() {
	m=read(); n=read();
	for(int i=1;i<=m;i++) 
		for(int j=1;j<=n;j++) {
			mp[i][j]=read(); 
			if(mp[i][j]>0) a[++len]={i, j, mp[i][j]};
		}
	
	res=len, ans=0;
	sort(a+1, a+1+len, cmp);
	memset(now, 63, sizeof(now));
	for(int i=1;i<=len;i++) {
		int x=a[i].x, y=a[i].y;
		if(now[x][y]>mp[x][y]) 
			bfs(x, y);
	}
	printf("%d\n", ans);
	return 0;
}

并查集的代码也贴上来了，仅供参考

#include<bits/stdc++.h>
using namespace std;
#define re register
const int maxn=1e3+5;
inline int read()
{
	char ch=getchar();bool f=0;int x=0;
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
	for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	if(f==1)x=-x;return x;
}
void print(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
int n,m,a[maxn][maxn],f[maxn][maxn],dx[4]={0,0,1,-1},dy[4]={1,-1,0,0},fa[maxn*maxn],s[maxn*maxnn],ans=0;
struct node
{
	int x,y,num;
}b[1000005];
bool cmp(node a,node b){return a.num<b.num;}int getf(int x){if(fa[x]==x)return x;fa[x]=getf(fa[x]);return x;}
void gett(int x,int y) {x=getf(x),y=getf(y);if(x==y)return ;fa[x]=y;s[y]|=s[x];}
int id(int x,int y){return (x-1)*m+y;}
signed main() {
	n=read(),m=read();memset(a,0x3f,sizeof a);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) {
			a[i][j]=read();
			if(a[i][j]<0)a[i][j]=abs(a[i][j]);
			else f[i][j]=1;
			b[id(i,j)]=(node){i,j,a[i][j]};
			fa[id(i,j)]=id(i,j);
		}
	sort(b+1,b+id(n,m)+1,cmp);
	for(int i=1;i<=n*m;i++) {
		for(int j=0;j<4;j++) {
			int tx=b[i].x+dx[j],ty=b[i].y+dy[j];
			if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]<=b[i].num)gett(id(tx,ty),id(b[i].x,b[i].y));
		}
		if(i==n*m||b[i].num!=b[i+1].num) {
			for(int j=i;j>=1&&b[j].num==b[i].num;j--) {
				if(f[b[j].x][b[j].y]) {
					int h=getf(id(b[j].x,b[j].y));
					if(!s[h])s[h]=1,ans++;
				}
			}
		}
	}
	cout<<ans;
 	return 0;
}