在具有给定边的两个权重的完整图中找到 MST 的权重

Question

我需要得到一个完整图的 MST，其中所有边的权重默认为 3，并且我还得到了权重为 1 的边。

这是一个例子

5 4 (N, M)
1 5
1 4
4 2
4 3

Resulting MST = 3 -> 5 -> 1 -> 4 -> 2

其中第一行包含总节点数 (N)、权重为 1 的边的数量 (M)，随后的所有 (M) 行都包含权重为 1 的边。

我尝试构建一个完整的图并将给定边的权重更新为 1，但是空间复杂度对于包含多达 10^5 个 1 权重边的问题来说太大了。

Answer 1

使用Kruskal 算法构造只有1 权重边的图的最小生成森林。整个图的最小生成树的总权重将是最小生成森林中的边数（乘以1）加上连接森林中树的边的成本（树数减去权重的1倍）的 3) 加上一个 3 权重边的成本，每个边连接不在原始最小生成森林中的剩余节点。