【题解】LuoGu5952：[POI2018]水箱

原题传送门
首先发现就是求一下把墙的高度看成边权，那么就求一个最小生成树，一边求，一边更新答案
对于两个连通块，维护$f祖先，h最大高度，num总方案数$
现在用$kruskal$连上一条长度为$l$的边
新的连通块的方案数是$(nu{m}_x+l-h_x)(nu{m}_y+l-h_y)$

Code：

#include <bits/stdc++.h>
#define maxn 1000010
#define LL long long
using namespace std;
const LL qy = 1000000007;
int n, m, H, tot, f[maxn], h[maxn];
struct Line{
	int x, y, len;
}line[maxn];
LL num[maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

bool cmp(Line x, Line y){ return x.len < y.len; }
int getfa(int k){ return f[k] == k ? k : f[k] = getfa(f[k]); }

int main(){
	n = read(), m = read(), H = read();
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j < m; ++j) line[++tot] = (Line){(i - 1) * m + j, (i - 1) * m + j + 1, read()};
	for (int i = 1; i < n; ++i)
		for (int j = 1; j <= m; ++j) line[++tot] = (Line){(i - 1) * m + j, i * m + j, read()};
	for (int i = 1; i <= n * m; ++i) f[i] = i, num[i] = 1 ;
	sort(line + 1, line + 1 + tot, cmp);
	for (int i = 1; i <= tot; ++i){
		int x = line[i].x, y = line[i].y, s1 = getfa(x), s2 = getfa(y), l = line[i].len;
		if (s1 != s2) num[s1] = (num[s1] + l - h[s1]) * (num[s2] + l - h[s2]) % qy, f[s2] = s1, h[s1] = l;
	}
	printf("%lld\n", (num[getfa(1)] + H - h[getfa(1)]) % qy);
	return 0;
}