题目链接
https://www.lydsy.com/JudgeOnline/problem.php?id=1104
思路
第一眼看上去是搜索？
这道题正解是带标记并查集，考虑一个城市的洪水能被抽走的情况，那样这个城市到出水口的高度都要小于城市的高度。并且，建立抽水机的区域一定是高度越小越好。
这样，对每个点和每个城市点分别排序后，枚举每个城市，将所有 相邻且高度均小于当前城市 的区域对 在并查集中合并，最后如果当前城市没有标记，说明需要在当前城市建立一个抽水机。
代码
#include <cstdio>
#include <cmath>
#include <algorithm>const int maxn=1000;
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};int n,m,h[maxn+10][maxn+10],cnt,ans;struct point
{int x,y;bool operator <(const point &other) const{return abs(h[x][y])<abs(h[other.x][other.y]);}
};point city[maxn*maxn+10],full[maxn*maxn+10];namespace dsu
{int fa[maxn*maxn+10],mark[maxn*maxn+10];int find(int x){return fa[x]?(fa[x]=find(fa[x])):x;}inline int merge(int x,int y){x=find(x);y=find(y);if(x==y){return 0;}fa[x]=y;if(mark[x]){mark[y]=1;}return 0;}
}inline int trans(int x,int y)
{return (x-1)*m+y;
}int main()
{scanf("%d%d",&n,&m);for(register int i=1; i<=n; ++i){for(register int j=1; j<=m; ++j){scanf("%d",&h[i][j]);if(h[i][j]>0){city[++cnt].x=i;city[cnt].y=j;}full[trans(i,j)].x=i;full[trans(i,j)].y=j;}}std::sort(city+1,city+cnt+1);std::sort(full+1,full+n*m+1);int now=1;for(register int i=1; i<=cnt; ++i){int xx=city[i].x,yy=city[i].y;while((now<=n*m)&&(abs(h[full[now].x][full[now].y])<=abs(h[xx][yy]))){int x=full[now].x,y=full[now].y;for(register int j=0; j<4; ++j){int nx=x+dx[j],ny=y+dy[j];if((nx<=0)||(nx>n)||(ny<=0)||(ny>m)){continue;}if(abs(h[nx][ny])<=abs(h[xx][yy])){dsu::merge(trans(x,y),trans(nx,ny));}}++now;}int fa=dsu::find(trans(xx,yy));if(!dsu::mark[fa]){dsu::mark[fa]=1;++ans;}}printf("%d\n",ans);return 0;
}
缩行之后的代码
（这是啥啊……）
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
const int maxn=1000;
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};
int f[maxn*maxn+10],mark[maxn*maxn+10],n,m,h[maxn+10][maxn+10],cnt,ans;
struct point{int x,y;bool operator <(const point &other)const{return abs(h[x][y])<abs(h[other.x][other.y]);}
}city[maxn*maxn+10],full[maxn*maxn+10];
int find(int x){return f[x]?(f[x]=find(f[x])):x;}
int merge(int x,int y){return (x=find(x))==(y=find(y))?0:f[x]=y,mark[x]&&(mark[y]=1);}
int trans(int x,int y){return (x-1)*m+y;}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){scanf("%d",&h[i][j]);(h[i][j]>0)&&(city[++cnt].x=i,city[cnt].y=j);full[trans(i,j)].x=i,full[trans(i,j)].y=j;}std::sort(city+1,city+cnt+1),std::sort(full+1,full+n*m+1);for(int i=1,now=1,xx,yy,fa;xx=city[i].x,yy=city[i].y,(i<=cnt);++i,fa=find(trans(xx,yy)),ans+=(!mark[fa])&&(mark[fa]=1))for(int x,y;(x=full[now].x),(y=full[now].y),((now<=n*m)&&(abs(h[full[now].x][full[now].y])<=abs(h[xx][yy])));++now)for(int j=0,nx,ny;nx=x+dx[j],ny=y+dy[j],j<4;++j){if((nx<=0)||(nx>n)||(ny<=0)||(ny>m))continue;if(abs(h[nx][ny])<=abs(h[xx][yy]))merge(trans(x,y),trans(nx,ny));}return printf("%d\n",ans),0;
}