对于“洪水问题”有什么有效的算法吗？

Question

我得找出堵车的降雨门槛。

所以，我必须打印降水的阈值来阻止交通。

(前)

3 3

0 1 2

1 2 3

0 2 6

产出:3

对于这个问题有什么好的算法或关键字吗？

谢谢

Answer 1

找到一个最大总洪水容量的生成树。该树中最小的边缘容量是网络断开的阈值。

“最大容量”树与边权等于负容量的最小权生成树相同，因此可以使用Kruskal或Prim算法找到这棵树。

显然，Kruskal的算法做的正是你想做的事情--按照下降容量的顺序处理边，直到网络连接：algorithm

令人惊讶的是，如果您不熟悉不相交的集合数据结构，那么它是非常快的。

任何寻找最小生成树的算法也会做同样的工作，但要证明这一点还需要做一点小小的工作。