← 返回题目列表

Codeforces · 1948/G

G. MST 与匹配

中文机器翻译题面 查看原题

给你一个 $$$n$$$ 个顶点上的无向连通图。该图的每条边都有一个权重;连接顶点 $$$i$$$ 和 $$$j$$$ 的边的权重为 $$$w_{i,j}$$$ (或者,如果 $$$i$$$ 和 $$$j$$$ 之间没有边,则 $$$w_{i,j} = 0$$$)。所有权重均为正整数。

您还将获得一个正整数 $$$c$$$。

你必须构建这个图的生成树;我。 e.精确选择该图的 $$$(n-1)$$$ 边,使得通过遍历某些选定的边,可以从每个其他顶点到达每个顶点。生成树的成本是两个值的总和:

- 所有选定边的权重之和;
- 生成树中的最大匹配(即一组边的最大大小,使得它们都属于所选的生成树,并且在该组中没有顶点具有多个事件边),乘以给定整数 $$$c$$$。

找到成本最小的生成树。由于图是连通的,因此至少存在一棵生成树。

输入

第一行包含两个整数 $$$n$$$ 和 $$$c$$$ ($$$2 \le n \le 20$$$; $$$1 \le c \le 10^6$$$)。

然后是 $$$n$$$ 行。其中第 $$$i$$$ 包含 $$$n$$$ 整数 $$$w_{i,1}, w_{i,2}, \dots, w_{i,n}$$$ ($$$0 \le w_{i,j} \le 10^6$$$),其中 $$$w_{i,j}$$$ 表示 $$$i$$$ 和 $$$i$$$ 之间的边的权重$$$j$$$ (或者 $$$w_{i,j} = 0$$$ 如果没有这样的边)。

输入的附加限制:

- 对于 [1, n]$$$ 中的每个 $$$i \, $$$w_{i,i} = 0$$$;
- 对于每对整数 $$$(i, j)$$$ 使得 $$$i \in [1, n]$$$ 和 $$$j \in [1, n]$$$, $$$w_{i,j} = w_{j,i}$$$;
- 给定的图已连接。

输出

打印一个整数 — 给定图的生成树的最小成本。

示例

输入 #1

4 10
0 1 8 0
1 0 1 0
8 1 0 2
0 0 2 0

输出 #1

21

输入 #2

4 5
0 1 8 0
1 0 1 0
8 1 0 2
0 0 2 0

输出 #2

14

注意

在第一个示例中,最小成本生成树由边 $$$(1, 3)$$$、$$$(2, 3)$$$ 和 $$$(3, 4)$$$ 组成。它的最大匹配是$$$1$$$。

在第二个示例中,最小成本生成树由边 $$$(1, 2)$$$、$$$(2, 3)$$$ 和 $$$(3, 4)$$$ 组成。它的最大匹配是$$$2$$$。