题目大意：给定一张地势图，，所有的点都被水淹没，现在有一些关键点，要求放最少的水泵使所有关键点的水都被抽干
前排感谢VFK
首先可以证明一定存在一种最优解使所有的水泵都在关键点上
那么我们将所有关键点按照高度排序，从小到大枚举每个关键点
对于每个关键点x，我们将所有高度小于等于x点的点都加入并查集并将相邻的合并
由于x是并查集中最高的点，因此并查集中任意一个点放置水泵都会导致点x被抽干
故如果x所在并查集中已经放置过水泵，则无需在x点放置水泵
否则就要在x点放置一个水泵
时间复杂度O(mnlog(mn))
一开始写了个O(1000mn)的SPFA结果T到死- –
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 1010using namespace std;struct abcd{int height,x,y;abcd() {}abcd(int _,int __,int ___):height(_),x(__),y(___) {}bool operator < (const abcd &a) const{return height < a.height;}}cities[M*M],map[M*M];int n,m,ans,tot;int a[M][M];namespace Union_Find_Set{pair<int,int> fa[M][M];bool pumped[M][M];pair<int,int> Find(pair<int,int> x){if(fa[x.first][x.second]==make_pair(0,0)||fa[x.first][x.second]==x)return fa[x.first][x.second]=x;return fa[x.first][x.second]=Find(fa[x.first][x.second]);}void Union(pair<int,int> x,pair<int,int> y){x=Find(x);y=Find(y);if(x==y) return ;fa[x.first][x.second]=y;pumped[y.first][y.second]|=pumped[x.first][x.second];}}void Insert(int x,int y){using namespace Union_Find_Set;static const int dx[]={1,-1,0,0};static const int dy[]={0,0,1,-1};int i;for(i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];if(xx<=0||yy<=0||xx>m||yy>n)continue;if(a[xx][yy]>a[x][y])continue;Union(make_pair(x,y),make_pair(xx,yy));}}int main(){using namespace Union_Find_Set;int i,j;cin>>m>>n;for(i=1;i<=m;i++)for(j=1;j<=n;j++){scanf("%d",&a[i][j]);if(a[i][j]>0)new (&cities[++tot])abcd(a[i][j],i,j);elsea[i][j]=-a[i][j];new (&map[i*n-n+j])abcd(a[i][j],i,j);}sort(cities+1,cities+tot+1);sort(map+1,map+m*n+1);for(j=1,i=1;i<=tot;i++){for(;j<=m*n&&map[j].height<=cities[i].height;j++)Insert(map[j].x,map[j].y);pair<int,int> temp=Find(make_pair(cities[i].x,cities[i].y));if(pumped[temp.first][temp.second])continue;++ans,pumped[temp.first][temp.second]=true;}cout<<ans<<endl;return 0;}
销售世界上第一号的产品——不是汽车，
