自动搬运

查看原文

来自洛谷，原作者为

	jdsb **

搬运于2025-08-24 22:15:56，当前版本为作者最后更新于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;
}