本文共 637 字，大约阅读时间需要 2 分钟。

正题

题目链接:

题目大意

$n\ast m$个格子，最外层有无限高的墙，然后每个格子之间有一睹给定高度的墙，然后求有多少种不同的水位情况。

解题思路

首先我们如果将墙看成边，那么会造成影响的一定是在最小生成树上的边，那么考虑一条边的影响，假设左边联通块墙最高为$h1$，右边为$h2$，左边水位都不高于$h1$时有$ans1$种方案，右边水位都不高于$h2$时有$ans2$中方案。该边的高度为$h$，那么新联通块的答案为$$(ans1+h-h1)\ast (ans2+h-h2)$$计算即可

$code$

#include
   
    #include
    
     #include
     
      #define ll long long#define p(x,y) ((x-1)*m+(y))using namespace std;const ll N=1e6+10,XJQ=1e9+7;struct node{
   	ll x,y,w;}a[N*4];ll n,m,H,tot,fa[N],ans[N],h[N];bool cmp(node x,node y){
   return x.w
     
    
   

转载地址：http://gdwaf.baihongyu.com/