我必须找出阻碍交通的下雨阈值。
所以，我必须打印降水阈值来阻止交通。
例如)
3 3
0 1 2
1 2 3
0 2 6
输出:3
这个问题有什么好的算法或者关键词吗？
谢谢
最佳答案
找到一棵具有最大总泛洪能力的生成树。该树中最小的边缘容量是网络断开连接的阈值。
“最大容量”树与边权等于负容量的最小权生成树相同，因此您可以使用 Kruskal 或 Prim 算法找到这棵树。
Kruskal 的算法显然完全符合您的要求——按照容量递减的顺序处理边缘，直到网络连接:https://en.wikipedia.org/wiki/Kruskal%27s_algorithm
令人惊讶的是，如果您不熟悉不相交的集合数据结构，它的速度非常快。
任何寻找最小生成树的算法也能完成同样的工作，但要证明这一点需要做一些工作。
关于algorithm - "flood problem?"是否有任何有效的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55466390/