给你一个 $$$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$$$。