CF1948G.MST with Matching

给定一个 $n$ 个点的无向连通图，令 $i, j$ 之间的边权为 $w_{i, j}$，若无边则 $w_{i, j} = 0$。

再给定一个常数 $c$。

你需要找到这个图的一个生成树，使得这个生成树的权值最小。定义一个生成树的权值为以下两者的和：

• 生成树中所有边权的和；
• 生成树上最大匹配的大小乘 $c$。

一个无向图 $G = (V, E)$ 的匹配为：一个边集 $E$ 的子集 $E'$，满足对于任意一个点 $i \in V$，不存在两条与 $i$ 相连的边 $(i, a), (i, b)$，使得 $(i, a), (i, b) \in E'$。

第一行，两个正整数 $n, c$​，表示图的点数与给定常数。

接下来 $n$ 行，第 $i$ 行 $n$ 个非负整数 $w_{i, j}$，表示 $(i, j)$ 的边权 。

输出一行一个整数，表示最小的生成树权值。

对于 $100 \%$ 的数据，保证 $2 \leq n \leq 20, 1 \leq c \leq 10^6, 0 \leq w_{i, j} \leq 10^6$。

保证 $w_{i, j} = w_{j, i}, w_{i, i} = 0$。

Translated by ShiRoZeTsu.