正題

題目鏈接:https://www.luogu.com.cn/problem/P5952

---

題目大意

$n?m$個格子，最外層有無限高的墻，然后每個格子之間有一睹給定高度的墻，然后求有多少種不同的水位情況。

---

解題思路

首先我們?nèi)绻麑闯蛇?#xff0c;那么會造成影響的一定是在最小生成樹上的邊，那么考慮一條邊的影響，假設左邊聯(lián)通塊墻最高為$h1$，右邊為$h2$，左邊水位都不高于$h1$時有$ans1$種方案，右邊水位都不高于$h2$時有$ans2$中方案。該邊的高度為$h$，那么新聯(lián)通塊的答案為$$(ans1+h?h1)?(ans2+h?h2)$$計算即可

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long #define p(x,y) ((x-1)*m+(y)) using namespace std; const ll N=1e6+10,XJQ=1e9+7; struct node{ll x,y,w; }a[N*4]; ll n,m,H,tot,fa[N],ans[N],h[N]; bool cmp(node x,node y) {return x.w<y.w;} ll find(ll x) {return (fa[x]==x)?(x):(fa[x]=find(fa[x]));} int main() {scanf("%lld%lld%lld",&n,&m,&H);for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++)fa[p(i,j)]=p(i,j),ans[p(i,j)]=1;for(ll i=1;i<=n;i++)for(ll j=1;j<m;j++){ll x;scanf("%lld",&x);a[++tot]=(node){p(i,j),p(i,j+1),x};}for(ll i=1;i<n;i++)for(ll j=1;j<=m;j++){ll x;scanf("%lld",&x);a[++tot]=(node){p(i,j),p(i+1,j),x};}sort(a+1,a+1+tot,cmp);for(ll i=1;i<=tot;i++){ll Fa=find(a[i].x),Fb=find(a[i].y);if(Fa!=Fb){ans[Fa]=(ans[Fa]+a[i].w-h[Fa])%XJQ*((ans[Fb]+a[i].w-h[Fb])%XJQ)%XJQ;fa[Fb]=Fa;h[Fa]=a[i].w; }}printf("%lld",(ans[find(1)]+H-h[find(1)])%XJQ); }

總結

以上是生活随笔為你收集整理的P5952-[POI2018]水箱【最小生成树】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。