题目描述
在地面上有一个水箱，它的俯视图被划分成了n行m列个方格，相邻两个方格之间有一堵厚度可以忽略不计的墙，水箱与外界之间有一堵高度无穷大的墙，因此水不可能漏到外面。已知水箱内每个格子的高度都是[0,H]之间的整数，请统计有多少可能的水位情况。因为答案可能很大，请对10^9+7取模输出。两个情况不同当且仅当存在至少一个方格的水位在两个情况中不同。
输入
第一行包含三个正整数n,m,H(n*m<=500000,1<=H<=10^9)。
接下来n行，每行m-1个整数a[i][j](1<=a[i][j]<=H)，表示(i,j)和(i,j+1)之间的墙的高度。
接下来n-1行，每行m个整数b[i][j](1<=b[i][j]<=H)，表示(i,j)和(i+1,j)之间的墙的高度。
输出
输出一行一个整数，即方案数模10^9+7的结果。
样例输入
3 2 2 1 1 1 1 2 1 1
样例输出
65
题解
并查集
首先容易发现，所有方格的连接是一个类似于最小生成树的过程。
因此我们先把每个隔板按照高度从小到大排序，然后一个一个加入。
对于每一个连通块，维护其：连通的最小高度（即最后加的一条边）$last[i]$ 、和连通之前的方案数 $v[i]$ 。
那么高度为 $z$ 时合并两个连通块 $x$ 和 $y$ ，形成新连通块的 $last$ 等于 $z$，方案数等于 $(v[x]+z-last[x])(v[y]+z-last[y])$ 。
如果最终的连通块为 $i$ ，则最后的答案即为 $v[i]+H-last[i]$ 。
时间复杂度 $O(nm\log n)$
#include#include #define N 500010#define mod 1000000007#define pos(i , j) ((i - 1) * m + j)using namespace std;typedef long long ll;struct data{ int x , y , z; data() {} data(int a , int b , int c) {x = a , y = b , z = c;} bool operator<(const data &a)const {return z < a.z;}}a[N << 1];int f[N] , last[N] , tot;ll v[N];int find(int x){ return x == f[x] ? x : f[x] = find(f[x]);}int main(){ int n , m , k , i , j , x , y; scanf("%d%d%d" , &n , &m , &k); for(i = 1 ; i <= n ; i ++ ) for(j = 1 ; j < m ; j ++ ) scanf("%d" , &x) , a[++tot] = data(pos(i , j) , pos(i , j + 1) , x); for(i = 1 ; i < n ; i ++ ) for(j = 1 ; j <= m ; j ++ ) scanf("%d" , &x) , a[++tot] = data(pos(i , j) , pos(i + 1 , j) , x); sort(a + 1 , a + tot + 1); for(i = 1 ; i <= n * m ; i ++ ) f[i] = i , last[i] = -1; for(i = 1 ; i <= tot ; i ++ ) { x = find(a[i].x) , y = find(a[i].y); if(find(x) != find(y)) v[y] = (v[y] + a[i].z - last[y]) * (v[x] + a[i].z - last[x]) % mod , last[y] = a[i].z , f[x] = y; } x = find(1); printf("%lld\n" , (v[x] + k - last[x]) % mod); return 0;}