题解：P3457 [POI2007] POW-The Flood

ty_mxzhn · 2024-08-13 19:01:49 · 题解

可以建出图来。假设 h_i \le h_j 并且 i,j 相邻，则连边 i \to j。

显然这有点像一个 DAG（但是并不是）。你可以把这个图缩点，答案是对缩点后的图拓扑，所有城市假设没被另一个城市支配掉就一定要放一个抽水机。

这个图论问题显然其实很经典。但是这个二维网格图显然有性质，所以你不需要这么写。你可以按照高度从低到高排序，每次处理一堆高度相等的点，如果所连接到的联通块里面还没有抽水机就放一个抽水机。

显然的，这样子做和之前的图论做法并没有什么本质区别。我们一开始只是想办法把他规约到了一个图论问题上而已。

代码很短。

#include <cstdio>
#include <algorithm>
using namespace std;

struct stu{
    int x,y,h,t;
    bool operator < (stu b)const{
        return h<b.h;
    }
}a[1000007];
int h[1007][1007],ps[1007][1007],fa[1000007],vi[1000007];
int n,m;
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]); 
}
int dx[]={0,0,-1,1},dy[]={-1,1,0,0};
void link(int x,int y){
    int r=find(ps[x][y]);
    for(int i=0;i<4;i++){
        int nx=x+dx[i],ny=y+dy[i];
        if(nx<1||nx>n||ny<1||ny>m) continue;
        int z=find(ps[nx][ny]);
        if(h[nx][ny]<=h[x][y]){
            fa[z]=r;
            vi[r]|=vi[z];
        }
    }
}
int ans;
void work(int x,int y){
    int r=find(ps[x][y]);
    if(vi[r]) return;
    vi[r]=true;
    ans++;
}
signed main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1,p;j<=m;j++){
            ps[i][j]=(i-1)*m+j;
            scanf("%d",&h[i][j]);
            if(h[i][j]>0) a[ps[i][j]].h=h[i][j],a[ps[i][j]].t=1;
            else h[i][j]=a[ps[i][j]].h=-h[i][j];
            a[ps[i][j]].x=i,a[ps[i][j]].y=j;
        }
    }
    for(int i=1;i<=n*m;i++) fa[i]=i;
    sort(a+1,a+n*m+1);
    a[0].h=a[n*m+1].h=-1001;
    for(int i=1;i<=n*m;i++){
        link(a[i].x,a[i].y);
        if(a[i].h!=a[i+1].h){
            for(int j=i;a[j].h==a[i].h;j--){
                if(a[j].t) work(a[j].x,a[j].y);
                //printf("%d ",a[j].h);
            }
            //printf("\n");
        }
    }
    printf("%d\n",ans);
    return 0;
}