【最小生成树】水箱（P5952）

正题
P5952

题目大意
有一个n*m的网格，每个网格之间有一个板，给出每个板的高度（边界有一个高度为

∞

/infty

∞ 的墙），在每个网格中注水（必须是非负整数），使得两个高度不等且相邻的网格之间有一个大于两边高度的板（可以理解为水的自由流动，如果没有板阻挡会过去），若最高高度为H，问合法的注水方案数

解题思路
考虑每一个网格网上注水会先越过哪个板，与另一个点高度同步
对每个板，建一条连接两个点的边，然后跑最小生成树，那么往上注水然后与别的格子同步一定之和这棵树上的边有关
证明：
如果存在一个点y和x相连，但是x和y的边不在最小生成树内，如果x在注水到x-y的高度之前都没有和y同步，那么最小生成树上x到y的路径最大权值就大

【最小生成树】水箱（P5952）最先出现在Python成神之路。