首页 > 代码库 > [POI2007]洪水pow 并查集
[POI2007]洪水pow 并查集
我们先得出一个结论：水泵要建在城市上。因为如果在非城市上建能把其他一些城市抽干，那么在城市上建也是一个效果（自己画图感性理解一下）
然后我们明白抽水的条件：周围的高度要>=自身的高度，这样会抽完它。如果低的话，会降低旁边位置的水位（这很重要）
然后我们枚举每一个城市，看它用不用建造。这样在每一个城市，枚举所有位置，看这个位置能不能被四周的抽干，这样用并查集维护，能抽干的都是一个祖先
这样枚举完一遍后，看这个城市所连的并查集有没有被抽干，如果没有，就在那里建造即可
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define pos(i,a,b) for(int i=(a);i<=(b);i++)#define pos2(i,a,b) for(int i=(a);i>=(b);i--)#define LL long long#define N 1010using namespace std;int map[N][N],n,m,cnt[N][N],ji,vis[N*N]; int fa[N*N],jicity,ans;struct haha{ int w,x,y;}cun[N*N],city[N*N];bool cmp(const haha &a,const haha &b){ return a.w<b.w;}int find(int x){ if(fa[x]!=x) fa[x]=find(fa[x]); return fa[x];}int main(){ memset(map,0x3f,sizeof(map)); scanf("%d%d",&n,&m); pos(i,1,n) pos(j,1,m){ scanf("%d",&map[i][j]); if(map[i][j]>0){ city[++jicity].w=map[i][j]; city[jicity].x=i;city[jicity].y=j; } else map[i][j]=-map[i][j]; cnt[i][j]=++ji; cun[ji].w=map[i][j]; cun[ji].x=i,cun[ji].y=j; } sort(cun+1,cun+ji+1,cmp);sort(city+1,city+jicity+1,cmp); pos(i,1,ji) fa[i]=i; int j=1; pos(i,1,jicity){ int cw=city[i].w,cx=city[i].x,cy=city[i].y; for(;j<=ji;j++){ int w=cun[j].w,x=cun[j].x,y=cun[j].y; if(cw<w) break; if(map[x][y]>=map[x+1][y]){ vis[find(cnt[x][y])]|=vis[find(cnt[x+1][y])]; fa[find(cnt[x+1][y])]=find(cnt[x][y]); } if(map[x][y]>=map[x][y+1]){ vis[find(cnt[x][y])]|=vis[find(cnt[x][y+1])]; fa[find(cnt[x][y+1])]=find(cnt[x][y]); } if(map[x][y]>=map[x-1][y]){ vis[find(cnt[x][y])]|=vis[find(cnt[x-1][y])]; fa[find(cnt[x-1][y])]=find(cnt[x][y]); } if(map[x][y]>=map[x][y-1]){ vis[find(cnt[x][y])]|=vis[find(cnt[x][y-1])]; fa[find(cnt[x][y-1])]=find(cnt[x][y]); } } if(!vis[find(cnt[cx][cy])]){ ans++;vis[find(cnt[cx][cy])]=1; } } cout<<ans; return 0;}
[POI2007]洪水pow 并查集
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。