【BZOJ5101】[POI2018]Powód
Description
在地面上有一个水箱，它的俯视图被划分成了n行m列个方格，相邻两个方格之间有一堵厚度可以忽略不计的墙，水箱与外界之间有一堵高度无穷大的墙，因此水不可能漏到外面。已知水箱内每个格子的高度都是[0,H]之间的整数，请统计有多少可能的水位情况。因为答案可能很大，请对10^9+7取模输出。两个情况不同当且仅当存在至少一个方格的水位在两个情况中不同。
Input
第一行包含三个正整数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)之间的墙的高度。
Output
输出一行一个整数，即方案数模10^9+7的结果。
Sample Input
3 2 2
1
1
1
1 2
1 1
1
1
1
1 2
1 1
Sample Output
65
HINT
要么全部格子水位都是2，要么全部格子水位都在[0,1]之间，共1+2^6=65种情况。
HINT
要么全部格子水位都是2，要么全部格子水位都在[0,1]之间，共1+2^6=65种情况。
题解：先将所有边按高度排序，然后从小到大枚举所有边，用并查集维护格子的连通性。在并查集合并的时候统计一下方案数就好。
具体地，我们用g表示当前连通块的方案数，h表示这个连通块当前的水位高度，设当前水位为now，于是一次合并的贡献就是(g+now-h)*(g'+now-h')。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define _(A,B) ((A-1)*m+B)
using namespace std;
typedef long long ll;
const ll P=1000000007;
const int maxn=500010;
int n,m,H,tot;
ll ans;
int f[maxn],h[maxn];
ll g[maxn];
struct node
{
int x,y,v;
node() {}
node(int a,int b,int c) {x=a,y=b,v=c;}
}p[maxn<<1];
bool cmp(const node &a,const node &b)
{
return a.v<b.v;
}
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+(gc^'0'),gc=getchar();
return ret*f;
}
int find(int x)
{
return (f[x]==x)?x:(f[x]=find(f[x]));
}
int main()
{
n=rd(),m=rd(),H=rd();
int i,j,a,b;
for(i=1;i<=n;i++) for(j=1;j<m;j++) p[++tot]=node(_(i,j),_(i,j+1),rd());
for(i=1;i<n;i++) for(j=1;j<=m;j++) p[++tot]=node(_(i,j),_(i+1,j),rd());
sort(p+1,p+tot+1,cmp);
for(i=1;i<=n*m;i++) f[i]=i,g[i]=1,h[i]=0;
for(i=1;i<=tot;i++)
{
a=p[i].x,b=p[i].y;
if(find(a)!=find(b))
{
g[f[b]]=(g[f[a]]+p[i].v-h[f[a]])*(g[f[b]]+p[i].v-h[f[b]])%P,h[f[b]]=p[i].v,f[f[a]]=f[b];
}
}
printf("%lld",(g[find(1)]+H-h[find(1)])%P);
return 0;
}