BZOJ5101 POI2018Powódź（并查集）

　　如果某个格子的积水量超过了该格子的某个挡板高度，那么挡板另一端的积水量就会与其相同。看起来是一个不断合并的过程，考虑并查集。枚举深度，维护每个连通块内的方案数，深度超过某挡板高度时，将两端的连通块合并，即方案数相乘。再加上该连通块均为当前深度的这种方案。这样复杂度即为O(nmHα)或O(n²m²α)。

　　注意到每次更新所有连通块的答案并没有意义，于是可以进一步优化，对每个连通块存储其已被更新到的深度，需要将其合并时再实际更新。复杂度即为O(nmα)。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 1000010

#define P 1000000007

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,m,h,fa[N],ans[N],cur[N],t;

struct data

{

    int x,y,z;

    bool operator <(const data&a) const

    {

        return z<a.z;

    }

}edge[N];

int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

int trans(int x,int y){return (x-)*m+y;}

int main()

{

#ifndef ONLINE_JUDGE

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

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

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read(),h=read();

    for (int i=;i<=n*m;i++) fa[i]=i,ans[i]=;

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

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

        t++,edge[t].x=trans(i,j),edge[t].y=trans(i,j+),edge[t].z=read();

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

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

        t++,edge[t].x=trans(i,j),edge[t].y=trans(i+,j),edge[t].z=read();

    sort(edge+,edge+t+);

    for (int i=;i<=t;i++)

    {

        int p=find(edge[i].x),q=find(edge[i].y);

        if (p!=q)

        {

            ans[p]+=edge[i].z-cur[p];

            ans[q]+=edge[i].z-cur[q];

            fa[q]=p;ans[p]=1ll*ans[p]*ans[q]%P;cur[p]=edge[i].z;

        }

    }

    cout<<(ans[find()]+h-cur[find()])%P;

    return ;

}

巴特西

BZOJ5101 POI2018Powódź（并查集）

最新文章

热门文章