BZOJ2936 Codevs3634 POI1999 积水

题目描述

有这样一块土地，它可以被划分成N×M个正方形小块，每块面积是一平方英寸，第i行第j列的小块可以表示成P(i,j)。这块土地高低不平，每一小块地P(i,j)都有自己的高度H(i,j)（单位是英寸）。

一场倾盆大雨后，这块地由于地势高低不同，许多低洼地方都积存了不少降水。假如你已经知道这块土地的详细信息，你能求出它最多能积存多少立方英寸的降水么？

输入格式

输入文件第一行有两个数，N，M（1<=N, M <=100），表示土地的规模是N×M平方英寸。

以下有N行，每行有M个整数，表示每块地的高低（每个整数在[1,10000]内，以英寸为单位）。

输出格式

输出文件只有一行，一个数，表示土地中最多能积存多少立方英寸的水。

样例输入

3 6

3 3 4 4 4 2

3 1 3 2 1 4

7 3 1 6 4 1

样例输出

先%一下yyf大神的题解

我们考虑一层一层地向图中加水

这样的话当我们考虑到v这个高度，所有小于v的高度我们都已经考虑过了

所以我们只考虑当前有多少个位置可以加入一层水

对于边界上的节点，我们需要排除掉，所以我们用0表示已经删除掉的集合，所以把需要删除的节点和0连接起来，否则的话我们需要维护高度相同的联通块的连通性，就把当前块和周围已经访问过的块连接起来就行了

所以用并查集维护siz

#include <bits/stdc++.h>

using namespace std;

#define N 110

#define V 10010

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

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

namespace Union_Find{

    int fa[V],siz[V];

    void init(int n){

        fa[0]=siz[0]=0;

        for(int i=1;i<=n;i++)fa[i]=i,siz[i]=1;

    }

    int find(int x){

        if(fa[x]==x)return x;

        return fa[x]=find(fa[x]);

    }

    void merge(int x,int y){

        int fx=find(x),fy=find(y);

        if(fx==fy)return;

        siz[fy]+=siz[fx];

        fa[fx]=fy;

    }

};

int n,m;

bool vis[N][N];

vector<pair<int,int> > g[V];

bool checkin(int x,int y){

    if(x<1||y<1||x>n||y>m)return 0;

    return 1;

}

int id(int x,int y){

    if(!checkin(x,y))return 0;

    return (x-1)*m+y;

}

int cnt=0,ans=0;

int main(){

    using namespace Union_Find;

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

    scanf("%d%d",&n,&m);

    init(n*m);

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

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

            int vl;scanf("%d",&vl);

            g[vl].push_back(pair<int,int>(i,j));

        }

    int up=n*m;

    for(int v=1;v<=V;v++){//考虑一层一层地加水

        if(siz[find(0)]==up)break;

        for(int j=0;j<g[v].size();j++){

            int x=g[v][j].first,y=g[v][j].second;

            vis[x][y]=1;

            cnt++;

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

                int nx=x+mx[k],ny=y+my[k];

                //如果当前点在边界上或者旁边有比它低的点就合并起来

                //在边界上siz[0]++ 说明这个点不可取

                //不在边界上维护可以到达的联通块

                if(!checkin(nx,ny)||vis[nx][ny])merge(id(nx,ny),id(x,y));

            }

        }

        ans+=cnt-siz[find(0)];

    }

    printf("%d",ans);

    return 0;

}

积水