水箱
题目链接:luogu P5952
题目大意
给你一个二维的矩阵,每个位置代表那个位置的水位,然后左右相连左右相连的位置都有一定高度的木板。
然后告诉你每个位置水位高度的上限,然后问你水位有多少种可能。
思路
不难发现一个特点,随着水位的增高,许多分开来(水位不同)的地方会合并。
那我们考虑“模拟”这个过程。
仔细想想就会发现这个过程你可以看做把每个水位看做点,然后木板看做边,那它就是要建一个最小生成树的过程。
那你就在合并的时候处理值即可。
具体一点的话就之前它本身的概率分别是 \(val_x,val_y\)(一开始全部都是 \(1\)),然后你记录它当前全部在一起的最低高度。(\(h_x,h_y\))
然后如果这次的高度是 \(w\),那新合并之后的 \(val\) 就是 \((val_x+w-h_x)(val_y+w-h_y)\)。
然后记得最后所有都合并完之后还有上升到限制高度的部分。
代码
#include<cstdio>
#include<algorithm>
#define ll long long
#define mo 1000000007
using namespace std;
int n, m, H, x, fa[500001], h[500001], tot;
struct node {
int s, t, w;
}w[1000001];
ll val[500001];
int get_bh(int x, int y) {
return (x - 1) * m + y;
}
bool cmp(node x, node y) {
return x.w < y.w;
}
int find(int now) {
if (fa[now] == now) return now;
return fa[now] = find(fa[now]);
}
int main() {
scanf("%d %d %d", &n, &m, &H);
for (int i = 1; i <= n * m; i++) {
fa[i] = i; val[i] = 1;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j < m; j++) {
scanf("%d", &x);
w[++tot] = (node){get_bh(i, j), get_bh(i, j + 1), x};
}
for (int i = 1; i < n; i++)
for (int j = 1; j <= m; j++) {
scanf("%d", &x);
w[++tot] = (node){get_bh(i, j), get_bh(i + 1, j), x};
}
sort(w + 1, w + tot + 1, cmp);
for (int i = 1; i <= tot; i++) {
int X = find(w[i].s), Y = find(w[i].t);
if (X == Y) continue;
fa[Y] = X;
val[X] = (val[X] + w[i].w - h[X]) * (val[Y] + w[i].w - h[Y]) % mo;
h[X] = w[i].w;
}
printf("%lld", (val[find(1)] + H - h[find(1)]) % mo);
return 0;
}