algorithm - "flood problem?"是否有任何有效的算法

Question

我必须找出阻碍交通的下雨阈值。

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

例如)
3 3
0 1 2
1 2 3
0 2 6
输出:3

这个问题有什么好的算法或者关键词吗？

谢谢

Answer 1

找到一棵具有最大总泛洪能力的生成树。该树中最小的边缘容量是网络断开连接的阈值。

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

Kruskal 的算法显然完全符合您的要求——按照容量递减的顺序处理边缘，直到网络连接:https://en.wikipedia.org/wiki/Kruskal%27s_algorithm

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

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