加权无向二分图在一个分区中连接所有节点的最小代价

Question

给定分区A和B之间的加权无向二分图，我试图找到连接分区A中所有节点的最小代价。

似乎我需要首先找到整个图的最小生成树(MST)，然后排除不必要的边(因为我不需要连接B分区中的节点)。我认为从MST中删除分区B中的节点，其程度为1(只连接到A分区的一个节点)，但在某些情况下，这种方法给出了次优的结果。

希望有人能帮我这个忙。

输入格式：

• 第一行是分区A和B的N和M大小(1 < N，M<1000)
• 其次是N的成本矩阵，第1行和第j列的值将是将Ai连接到Bj

的成本。

输出格式：

• 连接

中所有节点的最小成本

样本输入：

3 4
1 2 3 7
1 3 1 2
3 4 1 7

样本输出：

4

解释：

• 将A1连接到B1，A2连接到B1，A2连接到B3，A3连接到B3。

Answer 1

分区：A和B

节点：m和n (m，n< 1000)

我们正在尝试连接A中的所有节点

步骤1:创建A-节点对的详尽列表，连接它们需要最低成本。这将是(最大) mC2 = m * (m-1) / 2元素长列表。对于文章中的示例，如下所示：

[(A1,A2,2), (A1,A3,4), (A2,A3,2)]

这本质上是一个新的图，它的节点只来自A和相应的边权。实现这一点的最简单的方法是O(m^2 * n)

步骤2: --这将成为您的加权图，您可以应用MST逻辑得到您的最终答案，即O(m^2)解决方案(因为边数、~m^2、节点数、节点数、=m)。