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