正題

P5952

---

題目大意

有一個n*m的網格，每個網格之間有一個板，給出每個板的高度（邊界有一個高度為 $\infty$ 的墻），在每個網格中注水（必須是非負整數），使得兩個高度不等且相鄰的網格之間有一個大于兩邊高度的板（可以理解為水的自由流動，如果沒有板阻擋會過去），若最高高度為H，問合法的注水方案數

---

解題思路

考慮每一個網格網上注水會先越過哪個板，與另一個點高度同步

對每個板，建一條連接兩個點的邊，然后跑最小生成樹，那么往上注水然后與別的格子同步一定之和這棵樹上的邊有關

證明：

如果存在一個點y和x相連，但是x和y的邊不在最小生成樹內，如果x在注水到x-y的高度之前都沒有和y同步，那么最小生成樹上x到y的路徑最大權值就大于x-y的高度，不符合最小生成樹的定義，所以不存在這樣的情況

設 $h_x$ 為當前狀態下，x 所在連通塊的最高的板， $an{s}_x$ 為當前狀態下，x 所在連通塊到達最高的板的高度之前的方案數（因為超過最高的板后，可能注的水后超過后面增加的板）

對于每一次連邊，設 z 為當前板的高度，那么有 $ans=(an{s}_x+z?h_x)\times (an{s}_y+z?h_y)$，即兩邊的水可以選擇 $h+1～z$ 的高度，所以方案數加上z-h

最后得到的答案加上全部水覆蓋到H的方案數即可

---

code

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 500500 #define mp make_pair #define fs first #define sn second #define mod 1000000007 using namespace std; ll n,m,w,H,x,y,z,h[N],fa[N],ans[N]; pair<int,pair<int,int> >a[N<<1]; ll g(ll x,ll y) {return (x-1)*m+y; } ll find(ll x) {return x==fa[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){scanf("%lld",&x);a[++w]=mp(x,mp(g(i,j),g(i,j+1)));}for(ll i=1;i<n;++i)for(ll j=1;j<=m;++j){scanf("%lld",&x);a[++w]=mp(x,mp(g(i+1,j),g(i,j)));}sort(a+1,a+1+w);for(ll i=1;i<=n;++i)for(ll j=1;j<=m;++j){x=g(i,j);fa[x]=x;ans[x]=1;}for(ll i=1;i<=w;++i){x=find(a[i].sn.fs);y=find(a[i].sn.sn);z=a[i].fs;if(x==y)continue;fa[x]=y;ans[y]=(ans[x]+z-h[x]+mod)%mod*((ans[y]+z-h[y]+mod)%mod)%mod;h[y]=z;}x=find(1);printf("%lld",(ans[x]+H-h[x])%mod);return 0; }

總結

以上是生活随笔為你收集整理的【最小生成树】水箱（P5952）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。