G. 带匹配的最小生成树 详细题解

题目核心理解

给定一张 $n$ 个顶点的无向连通图，边权为 $w_{i,j}$，同时给定正整数 $c$。 你需要选出一棵原图的生成树，其代价为两部分之和：

1. 生成树所有边的权值之和；
2. 该生成树的最大匹配大小乘以 $c$。

求代价最小的生成树的代价。

核心思路

1. 关键性质

• 任意一棵树都是二分图，根据 Kőnig 定理： 树的最大匹配大小 = 树的最小点覆盖大小。
• 因此代价可以改写为： 边权和 $+\ c\times$ 最小点覆盖中点的数量。

2. 构造规则

• 枚举任意一个点集 $S$，把 $S$ 当作生成树的一个点覆盖。
• 只保留至少一个端点在 $S$ 中的边，在这些边里求最小生成树。
• 对每个 $S$ 计算代价：MST 边权和 $+\ c\times |S|$。
• 全局最小值即为答案。

算法流程

1. 枚举所有可能的点集 $S$（共 $2^n$ 个）。
2. 对每个 $S$，只使用满足 $u\in S$ 或 $v\in S$ 的边。
3. 在这些边中用 Prim 算法求最小生成树。
4. 计算当前代价：MST 权值和 $+\ c\times |S|$。
5. 所有合法情况取最小值，输出结果。

公式与复杂度分析

总代价公式：

复杂度

• 枚举点集：$O(2^n)$
• 单次 MST：$O(n^2)$
• 总时间复杂度：$O(2^n\cdot n^2)$

可轻松处理 $n\le 20$、$w_{i,j},c\le 10^6$ 的数据范围。