P5930 [POI1999] 降水

//木桶原理：桶能装的水的多少取决于最短的木板。
#include<iostream>
#include<cstdio>
#include<stack>
#include<cstring>
#include<queue>
using namespace std;
int n,m;
const int maxn=305;
int a[maxn][maxn];
bool vis[maxn][maxn];
struct node{
	int x,y,h;
	node(){}
	node(int _x,int _y,int _h){
		x=_x,y=_y,h=_h;
	}
	bool operator < (const node &_node)const {
		return h>_node.h;
	}
};
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int ans=0;
priority_queue<node>q;
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	bool flag=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d",&a[i][j]);
			if(i==1||j==1||i==n||j==m)q.push(node(i,j,a[i][j])),vis[i][j]=1;//把边上的高度全都压入堆中
		}
	}
	while(!q.empty()){
		int h=q.top().h,x=q.top().x,y=q.top().y;
		q.pop();
		for(int i=0;i<=3;i++){
			int tx=x+dx[i],ty=y+dy[i];
			if(vis[tx][ty]||tx<1||tx>n||ty<1||ty>m)continue;
			vis[tx][ty]=1;
			if(a[tx][ty]<h){
				// cout<<"hhh "<<h<<" "<<tx<<" "<<ty<<" "<<a[tx][ty]<<endl;
				ans+=(h-a[tx][ty]);
				q.push(node(tx,ty,h));
			}
			else q.push(node(tx,ty,a[tx][ty]));
		}
	}
	printf("%d\n",ans);
}
/*

4 5
3 5 8 8 2
4 2 2 6 7
6 1 2 2 9
7 8 9 6 4

3 5 8 8 2
4 2 2 6 7
6 1 3 5 9
7 8 9 6 4
思想好妙啊，外围一直在扩
如果比当前基准值要小，就继续扩
比如第二行第二列，变成4以后，考虑第三行第二列，+3
如果第三行第三列比4大，正好以4为基准
如果第三行第三列比4小，继续扩大外围
*/

//二维转一维并查集
//并查集的应用，非常妙的做法
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
vector<int> v[10005];
int n, m, mx, a[105][105], cnt, ans, fa[10005], size[10005];
int mvx[] = {0, 1, 0, -1};
int mvy[] = {1, 0, -1, 0};
const int lim = 10001;

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void uni(int x, int y){
    int v = find(x), u = find(y);
    // cout<<"v,u "<<x<<" "<<v<<" "<<u<<endl;
    if(u != v){
        fa[v] = u;
        size[u] += size[v];
        // cout<<"usize "<<size[u]<<endl;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            scanf("%d",&a[i][j]);
            v[a[i][j]].push_back(i * m + j);
            mx = max(mx, a[i][j]);
        }
    }
    for(int i = 0; i < n*m; i++) fa[i] = i, size[i] = 1;
    fa[lim] = lim, size[lim] = 0;
    for(int i = 1; i <= mx; i++){
        for(int j = 0; j < v[i].size(); j++){
            int p = v[i][j];
            int x = p/m , y = p%m;
            cnt++;//由原来的累加了当前高度为i的地区
            for(int k = 0; k <= 3; k++){
                int tx = x + mvx[k], ty = y + mvy[k];
                if(tx < 0 || tx >= n || ty < 0 || ty >= m){
                    uni(p, lim);
                    // cout<<"p "<<p<<" "<<size[lim]<<endl;
                }
                else if(a[tx][ty] <= a[x][y]){
                    uni(p, tx*m+ty);
                }
            }
        }
        // cout<<"cnt: "<<cnt<<" ,,,, find(lim) "<<size[find(lim)]<<endl;
        // cout<<"cnt-size[find(lim)] "<<cnt - size[find(lim)]<<endl;
        ans += cnt - size[find(lim)];

    }
    cout<<ans<<endl;
    return 0;
}