图-如何获得最小权连通子集？

Question

以下是消费税：

以下是我得到的：

>

我不得不假设权重是正负混合的。只有这两种重量的混合才有意义。

我会先对边进行排序，所以负边会在先。

我会考虑使用克鲁斯卡尔的算法，但应该有一些修改

因为我欢迎负边，所以我会尝试添加尽可能多的负边。

此外，一些正边可能被添加到只是在不是所有负边都连接的情况下，他们可能需要一些正边作为桥。

{0,1}的权重为-20

{2,3}的重量为-10

如果{1,3}的权重为11，那么我当然不想要{1,3}

这意味着仍然需要包括所有顶点。

而且它不仅仅是一个MST。假设一个顶点有两条边，一条是-1，另一条是-2。在一个普通的MST算法中，只有边-2将被采取。但在这个消费税中，都需要采取-1和-2以进一步减少整体重量。

Answer 1

我认为你的算法基本上已经是正确的了，但是只要稍加修改，实现起来就变得微不足道了。

首先，每一个负边必须包括，以最小化产生的权重。接下来，计算连接组件的数量C。如果c=1，就完成了。否则，您需要额外的C-1正边。

现在，当你添加负边时，把这看作是一个Kruskal的算法过程。每一个负边都可以把克鲁斯卡尔森林里的几棵树结合在一起。然而，即使负边的两端属于克鲁斯卡尔森林中的同一棵树，也要添加负边--不像通常的克鲁斯卡尔算法，在那里只添加联合两棵不同树的边。

以下是一些伪代码：

sort(edges);
c := n;
for edge in edges:
    if edge.weight < 0:
        if find(edge.firstEnd) != find(edge.secondEnd):
            --c;
        unite(edge.firstEnd, edge.secondEnd);
    else:
        if c == 1: break;
        if find(edge.firstEnd) != find(edge.secondEnd):
            unite(edge.firstEnd, edge.secondEnd);
            --c;

这里unite和find是不相交集数据结构的函数。