找到具有相同权重的最大边数的生成树
Find a spanning tree with maximum number of edges with same weight
问题来了。
给出一个带权无向连通图G。权重是恒定的。任务是提出一种算法，该算法可以找到满足这两个条件的 G 生成树的总权重（按优先级排序）：
- 生成树必须有相同权重的最大边数（实际重复的权重值无关）；
- 总的生成树权重应该最小化。这意味着，例如，权重为120的生成树T1最多有4条具有相同权重的边（并且这四个中的每一个的权重都是 15）应该优于权重为 140 的生成树 T2，它最多有 4 个边具有相同的权重（并且这四个中的每一个的权重都是 8）。
我已经坚持了很长一段时间了。我已经实现了图的Boruvka的MST搜索算法，现在我不确定是否应该在找到MST之后进行任何操作，还是修改MST搜索算法本身更好。
欢迎提出任何建议！
这在 O(m^2) 中可以天真地完成，而在 O(mn) 中不需要太多努力。似乎可以更快地完成它，可能像 O(m log^2(n)) 甚至 O(m log(n)) 那样需要一些工作。
基本思路是这样的。对于任何权重 k，设 MST(k) 是一棵生成树，它包含权重 k 的最大可能边数，否则具有最小总权重。可能有多棵这样的树，但它们的总重量都相同，所以你选择哪一棵并不重要。 MST(k) 可以通过使用任何 MST 算法并将权重 k 的所有边视为具有权重 -Infinity.
来找到
对于某些 k，此问题的解决方案将是 MST(k)。因此，天真的解决方案是生成所有 MST(k) 并选择具有最大数量的相同边权重然后最小总权重的那个。使用 Kruskal 算法，您可以在 O(m^2) 中执行此操作，因为您只需要对边缘进行一次排序。
这可以改进为 O(mn)，首先使用原始权重找到 MST，然后对于每个 k，通过减少每个树的权重将树修改为 MST(k)权重的边缘 k 到 -Infinity。更新 MST 以减少边权重是一个 O(n) 操作，因为您只需要在相应的 fundamental cycle.
中找到最大权重边
为了比 O(mn) 使用这种方法做得更好，您必须以这样一种方式预处理原始 MST，以便可以更快地执行这些边权重减少。似乎 heavy path decomposition 之类的东西应该可以在这里工作，但还有一些细节需要解决。
问题来了。
给出一个带权无向连通图G。权重是恒定的。任务是提出一种算法，该算法可以找到满足这两个条件的 G 生成树的总权重（按优先级排序）：
- 生成树必须有相同权重的最大边数（实际重复的权重值无关）；
- 总的生成树权重应该最小化。这意味着，例如，权重为120的生成树T1最多有4条具有相同权重的边（并且这四个中的每一个的权重都是 15）应该优于权重为 140 的生成树 T2，它最多有 4 个边具有相同的权重（并且这四个中的每一个的权重都是 8）。
我已经坚持了很长一段时间了。我已经实现了图的Boruvka的MST搜索算法，现在我不确定是否应该在找到MST之后进行任何操作，还是修改MST搜索算法本身更好。
欢迎提出任何建议！
这在 O(m^2) 中可以天真地完成，而在 O(mn) 中不需要太多努力。似乎可以更快地完成它，可能像 O(m log^2(n)) 甚至 O(m log(n)) 那样需要一些工作。
基本思路是这样的。对于任何权重 k，设 MST(k) 是一棵生成树，它包含权重 k 的最大可能边数，否则具有最小总权重。可能有多棵这样的树，但它们的总重量都相同，所以你选择哪一棵并不重要。 MST(k) 可以通过使用任何 MST 算法并将权重 k 的所有边视为具有权重 -Infinity.
对于某些 k，此问题的解决方案将是 MST(k)。因此，天真的解决方案是生成所有 MST(k) 并选择具有最大数量的相同边权重然后最小总权重的那个。使用 Kruskal 算法，您可以在 O(m^2) 中执行此操作，因为您只需要对边缘进行一次排序。
这可以改进为 O(mn)，首先使用原始权重找到 MST，然后对于每个 k，通过减少每个树的权重将树修改为 MST(k)权重的边缘 k 到 -Infinity。更新 MST 以减少边权重是一个 O(n) 操作，因为您只需要在相应的 fundamental cycle.
为了比 O(mn) 使用这种方法做得更好，您必须以这样一种方式预处理原始 MST，以便可以更快地执行这些边权重减少。似乎 heavy path decomposition 之类的东西应该可以在这里工作，但还有一些细节需要解决。