找到强连通图，使得最大边和最小边之间的差异最小
Find Strongly Connected Graph such that the difference between the maximum and minimum edges is minimum
给定一个有向加权图，它是强连通。我需要从这个图中找到一个 强连接的子图 使得 最大和最小权重边之间的差异 是 最小值。
为了更清楚，我需要去掉边，这样去掉边后，图仍然是强连通的并且最大和最小权重边之间的差异是最小值.
举个例子：
第一行是这个图的N个节点和M条边的个数。接下来的 M 行代表该图的边。
3 6
1 2 8
2 3 32
3 1 16
1 3 81
3 2 243
2 1 27
所选的 N 节点子图将包含边：
1 2 8
2 3 32
3 1 16
最大和最小权重边之差为：32 - 8 = 24。
所有选项中最小的那个。
我正在寻找最佳解决方案。最多有 3000 个节点和 5000 个边。
给定一个算法来测试给定的有向图 G = (V, E) 是否在 O(f(|V|, |E|)) 时间内强连通，这个问题可以在 O(| E|*f(|V|, |E|)) - 如果在已测试的有向图中添加或删除单个边后可以更快地完成强连通性测试，那就更好了。
按权重递增的顺序对边进行排序，并按此顺序对它们进行编号。最初，将第一条（权重最低的）边添加到所选边的集合 E'；只要 E' 不是强连通的，就向其添加下一条边。如果这个循环没有终止，那么 G 就不是强连通的。否则，当它停止时，在添加边 j 之后，假设我们包含边 1，我们已经找到了最小差分解 。将这个(1, j)解记录为现任
现在从 E' 中删除边 1，这样边 2 就是 E' 中剩余的权重最低的边。保留所有其他已确定的边，并再次开始添加下一个权重最低的边，从边 j+1 开始，直到形成 SCG。假设包含的最低权重边是边 i，对于每个 i <= |V|，可以重复计算最小差分解 。保持最好的整体。
注意求解起点i+1时，不必去掉为前一个起点i确定的边：如果边i，i+1，...，j- 1 不形成 SCG，则边 i+1, i+2, ..., j-1 也不形成 SCG。利用这个意味着整个外循环只运行 |E|次，而不是 O(|E|^2) 次。
给定一个有向加权图，它是强连通。我需要从这个图中找到一个 强连接的子图 使得 最大和最小权重边之间的差异 是 最小值。
为了更清楚，我需要去掉边，这样去掉边后，图仍然是强连通的并且最大和最小权重边之间的差异是最小值.
举个例子：
第一行是这个图的N个节点和M条边的个数。接下来的 M 行代表该图的边。
3 6
1 2 8
2 3 32
3 1 16
1 3 81
3 2 243
2 1 27
所选的 N 节点子图将包含边：
1 2 8
2 3 32
3 1 16
最大和最小权重边之差为：32 - 8 = 24。 所有选项中最小的那个。
我正在寻找最佳解决方案。最多有 3000 个节点和 5000 个边。
给定一个算法来测试给定的有向图 G = (V, E) 是否在 O(f(|V|, |E|)) 时间内强连通，这个问题可以在 O(| E|*f(|V|, |E|)) - 如果在已测试的有向图中添加或删除单个边后可以更快地完成强连通性测试，那就更好了。
按权重递增的顺序对边进行排序，并按此顺序对它们进行编号。最初，将第一条（权重最低的）边添加到所选边的集合 E'；只要 E' 不是强连通的，就向其添加下一条边。如果这个循环没有终止，那么 G 就不是强连通的。否则，当它停止时，在添加边 j 之后，假设我们包含边 1，我们已经找到了最小差分解 。将这个(1, j)解记录为现任
现在从 E' 中删除边 1，这样边 2 就是 E' 中剩余的权重最低的边。保留所有其他已确定的边，并再次开始添加下一个权重最低的边，从边 j+1 开始，直到形成 SCG。假设包含的最低权重边是边 i，对于每个 i <= |V|，可以重复计算最小差分解 。保持最好的整体。
注意求解起点i+1时，不必去掉为前一个起点i确定的边：如果边i，i+1，...，j- 1 不形成 SCG，则边 i+1, i+2, ..., j-1 也不形成 SCG。利用这个意味着整个外循环只运行 |E|次，而不是 O(|E|^2) 次。