问题就在这里。
给出一个带权无向连通图G。权重是恒定的。任务是提出一种算法，找到满足这两个条件的 G 的生成树的总权重（按优先级排序):
- 生成树必须有相同权重的最大边数（与实际重复重量值无关）；
-
应最小化总生成树重量。这意味着，例如，权重为 120 的生成树 T1（最多有 4 个相同权重的边（这四个边的权重均为 15））应该优于权重为 140 的生成树 T2（权重为 140）。最多 4 条边具有相同的权重（这 4 条边的权重均为 8）。
我已经坚持这个问题有一段时间了。我已经为图实现了Boruvka的MST搜索算法，现在我不确定是否应该在找到MST后执行任何操作，或者最好修改MST搜索算法本身。
欢迎任何建议！
这可以天真地完成O(m^2)，并且无需付出太多努力O(mn)。似乎可以做得更快，也许类似O(m log^2(n))甚至O(m log(n))只需一点工作。
基本的想法是这样的。对于任何体重k, let MST(k)是包含最大可能数量的权重边的生成树k，否则总重量最小。可能有多棵这样的树，但它们的总重量都相同，所以选择哪一棵并不重要。MST(k)可以通过使用任何 MST 算法并处理权重的所有边来找到k因为有重量-Infinity.
这个问题的解决方案将是MST(k)对于一些k。所以最简单的解决方案是生成所有MST(k)并选择具有最大数量的相同边权重和最小总权重的那个。使用 Kruskal 算法，您可以执行此操作O(m^2)因为您只需对边缘进行一次排序。
这可以改进为O(mn)首先使用原始权重找到 MST，然后对每个k，将树修改为MST(k)通过减少重量的每个边缘的重量k to -Infinity。更新 MST 以减少边缘权重是一种O(n)操作，因为你只需要找到相应的最大权重边基本周期 https://en.wikipedia.org/wiki/Cycle_basis#Fundamental_cycles.
为了做得比O(mn)使用这种方法，您必须对原始 MST 进行预处理，以便可以更快地执行这些边权重减少。似乎有类似的东西重路径分解 https://en.wikipedia.org/wiki/Heavy_path_decomposition应该可以在这里工作，但有一些细节需要解决。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
