DOC《这道题其实是最短路的变种,我们只需以出水点为源点,做...》

这道题其实是最短路的变种,我们只需以出水点为源点,做SPFA算法.

当然,我们要更新的不再是该点到源点的最短路径长度. 对于某个点,设T表示流完水后,此点的高度(如果上面没水,就是它本身的高度,否则就是水的高度).同时,T又可以表示此点到源点的路径上,经过的最小的T的值,毫无疑问,我们就是需要让每个点的T最小.并且,如果某点的T表示的是水的高度,他就可以被他周围的,比他小的T更新. 最后每个点的答案就是他的T减他本身的高度.期望得分70%. SPFA加入经典的SLF优化,就可以通过100%的数据了. 【CD打酱油的算法】 我的想法是按高度从小到大把矩阵的点加入.那么加入高度i的所有点后,新增的与出水口连通的所有点的最后水的高度就是i(特殊情况i>k,此时水的高度=max{该点的高度,k}). 这样的话,我们就可以先按高度排序,从小到大把相同高度的点加入矩阵,每次bellman-ford出与出水口连通的所有点.复杂度为O(N*M*(log(N*M))*N*M)可以过40%的数据. 于是我们还可以优化. 我们可以用并查集维护与出水口相连的连通块,每次加入连通块都是新增连通块的,所以并查后是一个树结构.于是就可以方便处理出所有新增的点了. 时间复杂度O (N*M*(log(N*M))+N*M) 可以过100%的数据. 用样例解释一下具体操作. 首先地图什么点都没有,现在加入高度为1的点: **1 **1 **1 这其实是加入了三个点不妨设为1-1-1 出水口没有加进来,所以没有地方需要标记. 然后加入高度为6的点: 6*1 **1 6*1 于是就有三棵还没有连通的树.6

6 1-1-1 加入高度为7的点: 6*1 7*1 6*1 有7的存在两个6并到7那里,于是就有两棵树了:

7 1-1-1 / \

6 6 接着加入高度为8的点,所有连成一棵树.

8 ------8 / \

7 1-1-1 / \

6 6 由于有一个8是出水口,于是目前的所有点都是新增的点,所以现在所有点的最终水的高度都是8 加入高度为9的点:

9 |

8 ------8 / \

7 1-1-1 / \

6 6 于是9是新增的点,是在加入高度为9后才新增的所以9的最后水的高度为9. 这棵树代表的是连通块是在加入什么高度的点后才连通,也就是yxr的算法中要用SPFA求的T值.在树上具体就是任意两个格子之间的T值就是这两个格子在树上的LCA数值. 但是这题不用具体求LCA,只要遍历一下这棵树就可以知道答案了.答案就是所有点在树上与出水口的LCA. 遍历的时候从根到出水口的路径上的所有点标记.那么只要一个点标记了那么自己的高度就是自己的T值,否则就是自己父亲的T值.这个只要了解LCA的性质就可以很简单地推出来了.