【Luogu3457】POW-The Flood（并查集）

题面

洛谷

题解

我们知道，如果一个点和一个海拔不高于它的点相连

那么连在那个点是更优的，所以考虑按照每个点的海拔排序

既然按照海拔排序，相邻的海拔递增的点可以放在同一个集合里面讨论

考虑使用并查集，每一个集合中只需要有一个抽水机即可

每次从海拔最低的点中选出一个点

将它和它周围的海拔比当前海拔低的点直接链接在一起

同时，维护每个并查集是否存在抽水机

如果当前点是城市，并且所在的并查集中有抽水机了

显然是不用再额外增加抽水机了

但是，如果当前点和周围的点合并完之后，所在集合依然没有抽水机

因为它所在的集合周围的点海拔一定更高，不可能有抽水机

所以在当前集合中一点要放一个抽水机，

那么，给当前集合放一个抽水机，同时答案加一即可

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 1010

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int n,m,g[MAX][MAX],bh[MAX][MAX];

struct Node{int id,x,y,w;}p[MAX*MAX];

bool operator<(Node a,Node b){return a.w<b.w;}

int f[MAX*MAX],pl[MAX*MAX],tot,ans;

int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}

int d[4][2]={1,0,-1,0,0,1,0,-1};

void Merge(int u,int v)

{

	pl[getf(v)]|=pl[getf(u)];

	f[getf(u)]=getf(v);

}

int main()

{

	freopen("pow.in","r",stdin);

	freopen("pow.out","w",stdout);

	n=read();m=read();

	memset(g,-63,sizeof(g));

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j)

			g[i][j]=read();

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j)

			p[++tot]=(Node){bh[i][j]=tot,i,j,abs(g[i][j])};

	for(int i=1;i<=tot;++i)f[i]=i;

	sort(&p[1],&p[tot+1]);

	for(int i=1;i<=tot;++i)

	{

		int X=p[i].x,Y=p[i].y;

		for(int k=0;k<4;++k)

		{

			int x=p[i].x+d[k][0],y=p[i].y+d[k][1];

			if(abs(g[x][y])<=abs(g[X][Y]))Merge(getf(bh[x][y]),getf(bh[X][Y]));

		}

		if(abs(p[i+1].w)!=abs(p[i].w))

			for(int j=i;abs(p[j].w)==abs(p[i].w);--j)

				if(g[p[j].x][p[j].y]>0)

				{

					int u=getf(bh[p[j].x][p[j].y]);

					if(!pl[u])pl[u]=1,++ans;

				}

	}

	printf("%d\n",ans);

	return 0;

}