设G = (V,E)为无向图。让w(e)是一个具有正权重的加权函数。让是关于T的最小生成树。Gw
给定一组边S，其中S是 的子集E(G)，定义一个新的加权函数Q，Q(e) = w(e)如果e不在S，Q(e) = w(e)+100如果e在S。设计一个算法，接受作为输入 , ,G和一个集合，并输出一个最小生成树 wrt 。使其及时运行。TwS|S| = 10QO(V+E)
好的：自从我最初提出这个问题以来，我了解到的是，对 MST 进行分区是为了“分解”一条边，这会产生两个独立的组件，每个 MST 的顶点都是它们自己组件中的顶点。因此，在这个问题中，S 中的边可能会将 MST 分解为更小的 MST（11，对吗？）。我必须找到将一个组件连接到另一个组件的最轻的边缘。
我的计划是从一个顶点开始并使用 BFS 进行扩展，直到我涵盖所有这些组件。对于组件中的每个 u，u.color = black. 然后，我返回并再次用 BFS 覆盖组件，这次找到所有连接到非黑色顶点的边，因此不包含在组件中，并穿过现有的切口。与这些边相对的顶点被放置在队列 R 中。一旦我完成，我u = RemoveMin(R)就是运行O(lgE)。因为它只会在我每次覆盖一个组件时被调用，所以它总体上运行的最大值是10*O(lgE)，仍然是O(lgE). 因此，一旦删除 u，我就会对新组件执行 BFS，以便该组件中的所有 u.color = black。我再次遍历所有黑色顶点，以便我可以将所有带有更新键的白色顶点排队到 R 中。我做u = RemoveMin(R).
所以我真的认为这是可行的并且是可以证明的。任何人都可以提出类似的建议吗？
任何帮助，无论多么小，都将不胜感激。