Bzoj1104 [POI2007]洪水pow

Description

https://www.luogu.com.cn/problem/P3457

Solution

丹砂成功了，但是做完看题解发现想复杂了。/kk

首先，观察到如果在 $x$ 放抽水机能把 $y$ 中的水抽干，当且仅当存在一条路径，路径上的点都 $\le h_y$。

这启发我们给所有点按海拔排序。

并查集维护满足在这个点放抽水机使得 $x$ 被抽干的连通块。

然后观察到如果在不是城市的点放抽水机肯定不优。我们直接钦定把饮水机放在当前连通块中是城市且高度最小的点上。并查集维护连边的方向。这样贪心感觉很对。

复杂度 $O(nm)$，要乘上并查集复杂度（一般我认为是常数）。

---

写完之后看题解，发现如果合并时当前点为城市且连通块没有饮水机就在当前城市放，这样更好写啊，而且和上面啊的做法似乎本质相同。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 1005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,m;
int id(int x,int y) {return (x-1)*m+y;}
int a[maxn][maxn],vis[maxn][maxn];
int fa[maxn*maxn*4],t[maxn*maxn],g[maxn*maxn],ans=0;
int fx[5]={1,-1,0,0},fy[6]={0,0,1,-1};
int getfa(int x) {return x==fa[x]?x:fa[x]=getfa(fa[x]);}
vector<pair<int,int> >O[maxn];
signed main(void){
	int i,x,j,k,l;
	read(n);read(m);
	for (i=1;i<=n;i++) 
		for (j=1;j<=m;j++) {
			read(x);
			if (x>0) a[i][j]=x,vis[i][j]=1;
			else a[i][j]=-x;
			fa[id(i,j)]=id(i,j);
			if (vis[i][j]) g[id(i,j)]=a[i][j];
			else g[id(i,j)]=1e9;
			O[a[i][j]].push_back(mk(i,j));
		}
	for (l=0;l<=1000;l++) {
		for (auto tmp:O[l]) {
			i=tmp.fi,j=tmp.se;
			int Min=a[i][j],idx=0,idy=0;
			for (k=0;k<4;k++) {
				int xx=i+fx[k],yy=j+fy[k];
				if (xx&&yy&&xx<=n&&yy<=m&&a[xx][yy]<=a[i][j]) {
					if (g[getfa(id(xx,yy))]<=g[getfa(id(i,j))]) {
						fa[getfa(id(i,j))]=getfa(id(xx,yy));
					}
					else fa[getfa(id(xx,yy))]=getfa(id(i,j));
				} 
			}
		}
		for (auto tmp:O[l]) {
			i=tmp.fi,j=tmp.se;
			if (vis[i][j]) t[getfa(id(i,j))]=1,x=getfa(id(i,j));//,gdb(l,i,j,(x-1)/m+1,(x-1)%m+1);
		}
	}
	for (i=1;i<=n*m;i++) ans+=t[i];
	printf("%d\n",ans);
	return 0;
}
//i=begin && g++ $i.cpp -o $i -std=c++14 && ./$i