P5952题解
题目描述
在地面上有一个水箱，它的俯视图被划分成了 \(n\) 行 \(m\) 列个方格，相邻两个方格之间有一堵厚度可以忽略不计的墙，水箱与外界之间有一堵高度无穷大的墙，因此水不可能漏到外面。已知水箱内每个格子的高度只能是 \([0,H]\) 之间的整数，请统计有多少可能的水位情况。
因为答案可能很大，请对 \(10^9+7\) 取模输出。
我们说两种情况是不同的当且仅当存在至少一个方格的水位在两个情况中不同。
题解
这是一道网格图转最小生成树的巧妙题，本质是木桶效应。
根据样例，不难发现连通块的算法。但是怎样确定计算的顺序呢？
我们考虑从小加边，跑最小生成树，对合并的连通块算贡献，因为其他的墙均高于当前，因此不会产生新的连通块，这样顺序就确定了。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
const int N=5e5+100;
int n,m,H,fa[N],h[N],ans[N];
struct node{
int u,v,val;
bool operator < (const node &x) const
{
return val<x.val;
}
};
vector<node>p;
int id(int x,int y)
{
return (x-1)*m+y;
}
int find(int x)
{
if(fa[x]!=x)
{
fa[x]=find(fa[x]);
}
return fa[x];
}
void merge(int x,int y,int v)
{
x=find(x),y=find(y);
ans[x]=(((ans[x]+v-h[x])%mod)*((ans[y]+v-h[y])%mod))%mod;
h[x]=v;
fa[y]=x;
return;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m>>H;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
fa[id(i,j)]=id(i,j);
ans[id(i,j)]=1;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<m;j++)
{
int x;
cin>>x;
p.push_back(node{id(i,j),id(i,j+1),x});
}
}
for(int i=1;i<n;i++)
{
for(int j=1;j<=m;j++)
{
int x;
cin>>x;
p.push_back(node{id(i,j),id(i+1,j),x});
}
}
sort(p.begin(),p.end());
for(int i=0;i<p.size();i++)
{
if(find(p[i].u)==find(p[i].v))
continue;
merge(p[i].u,p[i].v,p[i].val);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(find(id(i,j))==id(i,j))
{
cout<<(ans[id(i,j)]-h[id(i,j)]+H)%mod;
return 0;
}
}
}
return 0;
}