题解 P5952 【[POI2018]水箱】

jdsb · 2020-07-28 21:26:43 · 题解

题意

给定一个高为H的水箱，水箱被划分为n*m个格子，每个相邻的格子之间都有一堵墙，高度为h_i，每个格子高度都是[0,H]之间的整数，求有多少种可能的水位情况。

分析

• 我们将每堵墙看作边，边的边权为墙的高度，再把墙两边的格子看作点，可以发现只有这张图上的最小生成树上的边才是会对答案有影响的，我们来证明一下这个东西。

• 设已经有两个点 x，y，被我们所选中，这两个点所处的连通块的高度为 h，此时有一条边能使 x，y 相连，这条边的边权为 h'，若 h'>h，则这个连通块的最高的能不相同的水位高度也只能为h，所以h'对答案没有贡献。

• 当我们知道了这个结论，我们就可以来做这道题了。我们先把边按照边权从小到大排序，然后对于这条边的两个结点 u，v，若这两个点不在一个连通块中，我们就考虑合并它们的答案，设 f_u 和 f_v 分别为两个联通块的答案，h_u 和 h_v 为两个连通块的最高高度，v 为这条边的边权，则新的联通块的答案就为 (f_u+v-h_u)*(f_v+v-h_v)，因为左边连通块的最高高度本来为 h_u，现在最高高度变为 v，那么左边的方案就增加了 v-h_u，右边也是同理，根据乘法原理，即可得到上面的式子，那么这题就做完了。

代码

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();};
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x*f;
}
#define ll long long
const int N=5e5+5,mod=1e9+7;
struct edge
{
    int x,y,v;
}e[N<<1];
int cnt;
bool mycmp(edge x,edge y)
{
    return x.v<y.v;
}
int f[N];
int get(int x)
{
    if(x^f[x]) f[x]=get(f[x]);
    return f[x];
}
int n,m,H,ans[N],h[N];
int ya(int x,int y)
{
    return (x-1)*m+y;
}
int main()
{
    n=read(),m=read(),H=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<m;j++)
        {
            int x=ya(i,j),y=ya(i,j+1),v=read();
            e[++cnt]={x,y,v}; 
        }
    for(int i=1;i<n;i++)
        for(int j=1;j<=m;j++)
        {
            int x=ya(i,j),y=ya(i+1,j),v=read();
            e[++cnt]={x,y,v};
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            int x=ya(i,j);
            f[x]=x;
            ans[x]=1;
        }
    sort(e+1,e+cnt+1,mycmp);
    for(int i=1;i<=cnt;i++)
    {
        int x=get(e[i].x),y=get(e[i].y),v=e[i].v;
        if(x^y)
        {
            f[y]=x;
            ans[x]=1ll*(ans[x]-h[x]+v)*(ans[y]-h[y]+v)%mod;
            h[x]=v;
        }
    }
    int x=get(1);
    printf("%d\n",(ans[x]-h[x]+H)%mod);
    return 0;
}