题目链接

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; }