题目描述：
有一块矩形土地被划分成$n$ $*$ $m$个正方形小块。这些小块高低不平，每一小块都有自己的高度。水流可以由任意一块地流向周围四个方向的四块地中，但是不能直接流入对角相连的小块中。
一场大雨后，由于地势高低不同，许多地方都积存了不少降水。给定每个小块的高度，求每个小块的积水高度。
注意：假设矩形地外围无限大且高度为$0$。
输入格式：
第一行两个非负整数$n$，$m$。
接下来一个$n$ $*$ $m$的矩阵，表示每个小块的高度。
输出格式：
输出一个$n$ $*$ $m$的矩阵，表示每个小块的积水高度。
输入样例：
3 3 4 4 0 2 1 3 3 3 -1
输出样例：
0 0 0 0 1 0 0 0 1
数据范围：
$n$，$m$ $≤$ $300$，小块高度 $≤$ $10$9；
思路：
首先可以了解到积水高度和周围最高的小块的高度有关。
对于小块$i$，它的积水高度会与四周最高的山峰的最低值相等，如木桶原理。
因此可以考虑对于每个小块$i$，将它与它四周的小块连边，边权为两座山峰中的最大值，然后跑最小生成树，最后通过dfs求得周围最高山峰中的最低的那一个即为它的积水高度。
对于在边界上的小块，只需要与定义$0$号点为边界外的点连边，然后$0$号点的高度为$0$。
代码：
1 #include <bits/stdc++.h> 2 #define INF 0x3f3f3f3f 3 using namespace std; 4 int n, m, q[1010][1010], z, fa[1000010], num, head[1000010]; 5 struct Tree {int x, y, z;}tree[2000010]; 6 struct node {int next, to, val;}stu[2000010]; 7 int cmp(Tree a, Tree b) {return a.z < b.z;} 8 int find(int x) {return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);} 9 void unity(int x, int y) {fa[find(x)] = find(y); return;} 10 void add(int x, int y, int z) {stu[++num].next = head[x], stu[num].to = y, stu[num].val = z, head[x] = num; return;} 11 void edge(int ax, int ay, int bx, int by) 12 { 13 int numa, numb; 14 if(ax < 1 || ay < 1 || ax > m || ay > n) numa = 0; else numa = (ax - 1) * m + ay; 15 if(bx < 1 || by < 1 || bx > m || by > n) numb = 0; else numb = (bx - 1) * m + by; 16 tree[++z].x = numa, tree[z].y = numb, tree[z].z = max(q[ax][ay], q[bx][by]); 17 tree[++z].x = numb, tree[z].y = numa, tree[z].z = max(q[ax][ay], q[bx][by]); 18 return; 19 } 20 void kruskal() 21 { 22 for(int i = 1; i <= n * m; ++i) fa[i] = i; 23 sort(tree + 1, tree + z + 1, cmp); 24 for(int i = 1; i <= z; ++i) 25 { 26 if(find(tree[i].x) != find(tree[i].y)) 27 { 28 unity(tree[i].x, tree[i].y); 29 add(tree[i].x, tree[i].y, tree[i].z), add(tree[i].y, tree[i].x, tree[i].z); 30 } 31 } 32 return; 33 } 34 void dfs(int u, int father, int sum) 35 { 36 for(int i = head[u]; i; i = stu[i].next) 37 { 38 int k = stu[i].to; 39 if(k == father) continue; 40 int xx = k / m + 1, yy = k % m; 41 if(!yy) --xx, yy = m; 42 q[xx][yy] = max(sum, stu[i].val) - q[xx][yy]; 43 dfs(k, u, max(sum, stu[i].val)); 44 } 45 return; 46 } 47 int main() 48 { 49 scanf("%d %d", &n, &m); 50 for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) scanf("%d", &q[i][j]); 51 for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) edge(i, j, i - 1, j), edge(i, j, i + 1, j), edge(i, j, i, j - 1), edge(i, j, i, j + 1); 52 kruskal(); 53 dfs(0, -1, -INF); 54 for(int i = 1; i <= n; ++i) {for(int j = 1; j <= m; ++j) printf("%d ", q[i][j]); puts("");} 55 return 0; 56 }