题解P3457 [POI2007]POW-The Flood

louhao088 · 2021-08-26 10:55:42 · 题解

一道贪心好题。

首先我们发现如果在他周围比他低的点有抽水机，那么他肯定不用再放抽水机了。

很自然的得到一个想法，就是把所有点按高度排序。依次判断要抽水的点四周能连出去的点中是否有抽水机。

这个操作可以用并查集维护，把高的点放入四周低的点的并查集中，每次查询他所在并查集有没有抽水机，没有就加上。

可以证明这样操作能使答案最优。

时间复杂度 O( nm \log{nm}) 。

代码如下

#include<bits/stdc++.h>
using namespace std;
//static char buf[1000000],*p1=buf,*p2=buf;
//#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
#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*maxn],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 fa[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()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    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(a[tx][ty]<=b[i].num)gett(id(tx,ty),id(b[i].x,b[i].y));
        }
        if(b[i].num!=b[i+1].num)
        {
            for(int j=i;;j--)
            {
                if(b[j].num!=b[i].num)break;
                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;
}

如有帮到你，请点赞支持，谢谢。