311196: CF1948G. MST with Matching
Description
You are given an undirected connected graph on $n$ vertices. Each edge of this graph has a weight; the weight of the edge connecting vertices $i$ and $j$ is $w_{i,j}$ (or $w_{i,j} = 0$ if there is no edge between $i$ and $j$). All weights are positive integers.
You are also given a positive integer $c$.
You have to build a spanning tree of this graph; i. e. choose exactly $(n-1)$ edges of this graph in such a way that every vertex can be reached from every other vertex by traversing some of the chosen edges. The cost of the spanning tree is the sum of two values:
- the sum of weights of all chosen edges;
- the maximum matching in the spanning tree (i. e. the maximum size of a set of edges such that they all belong to the chosen spanning tree, and no vertex has more than one incident edge in this set), multiplied by the given integer $c$.
Find any spanning tree with the minimum cost. Since the graph is connected, there exists at least one spanning tree.
InputThe first line contains two integers $n$ and $c$ ($2 \le n \le 20$; $1 \le c \le 10^6$).
Then $n$ lines follow. The $i$-th of them contains $n$ integers $w_{i,1}, w_{i,2}, \dots, w_{i,n}$ ($0 \le w_{i,j} \le 10^6$), where $w_{i,j}$ denotes the weight of the edge between $i$ and $j$ (or $w_{i,j} = 0$ if there is no such edge).
Additional constraints on the input:
- for every $i \in [1, n]$, $w_{i,i} = 0$;
- for every pair of integers $(i, j)$ such that $i \in [1, n]$ and $j \in [1, n]$, $w_{i,j} = w_{j,i}$;
- the given graph is connected.
Print one integer — the minimum cost of a spanning tree of the given graph.
ExamplesInput4 10 0 1 8 0 1 0 1 0 8 1 0 2 0 0 2 0Output
21Input
4 5 0 1 8 0 1 0 1 0 8 1 0 2 0 0 2 0Output
14Note
In the first example, the minimum cost spanning tree consists of edges $(1, 3)$, $(2, 3)$ and $(3, 4)$. The maximum matching for it is $1$.
In the second example, the minimum cost spanning tree consists of edges $(1, 2)$, $(2, 3)$ and $(3, 4)$. The maximum matching for it is $2$.
Output
给定一个无向连通图，包含n个顶点。图中每条边都有一个正整数的权重；连接顶点i和j的边的权重是w_{i,j}（如果i和j之间没有边，则w_{i,j}=0）。另外给定一个正整数c。
需要构建这个图的一个生成树；即选择恰好(n-1)条边，使得每个顶点都可以通过遍历某些选定的边到达其他每个顶点。生成树的成本是两个值的和：
1. 所有选定边的权重之和；
2. 生成树中的最大匹配（即边的最大集合，它们都属于选定的生成树，且没有顶点在此集合中有多于一条的关联边）乘以给定的整数c。
求解具有最小成本的任意生成树。由于图是连通的，至少存在一个生成树。
输入输出数据格式：
输入：
第一行包含两个整数n和c（2≤n≤20；1≤c≤10^6）。
接下来n行，每行包含n个整数w_{i,1}, w_{i,2}, …, w_{i,n}（0≤w_{i,j}≤10^6），其中w_{i,j}表示顶点i和j之间边的权重（如果i和j之间没有边，则w_{i,j}=0）。
输入的额外限制条件：
- 对于每个i∈[1, n]，w_{i,i}=0；
- 对于每对整数(i, j)，其中i∈[1, n]和j∈[1, n]，w_{i,j}=w_{j,i}；
- 给定的图是连通的。
输出：
打印一个整数，即给定图的最小成本生成树的成本。
示例：
输入：
4 10
0 1 8 0
1 0 1 0
8 1 0 2
0 0 2 0
输出：
21
输入：
4 5
0 1 8 0
1 0 1 0
8 1 0 2
0 0 2 0
输出：
14
注意：
在第一个示例中，最小成本生成树由边(1, 3), (2, 3)和(3, 4)组成。其最大匹配为1。
在第二个示例中，最小成本生成树由边(1, 2), (2, 3)和(3, 4)组成。其最大匹配为2。题目大意： 给定一个无向连通图，包含n个顶点。图中每条边都有一个正整数的权重；连接顶点i和j的边的权重是w_{i,j}（如果i和j之间没有边，则w_{i,j}=0）。另外给定一个正整数c。 需要构建这个图的一个生成树；即选择恰好(n-1)条边，使得每个顶点都可以通过遍历某些选定的边到达其他每个顶点。生成树的成本是两个值的和： 1. 所有选定边的权重之和； 2. 生成树中的最大匹配（即边的最大集合，它们都属于选定的生成树，且没有顶点在此集合中有多于一条的关联边）乘以给定的整数c。 求解具有最小成本的任意生成树。由于图是连通的，至少存在一个生成树。 输入输出数据格式： 输入： 第一行包含两个整数n和c（2≤n≤20；1≤c≤10^6）。 接下来n行，每行包含n个整数w_{i,1}, w_{i,2}, …, w_{i,n}（0≤w_{i,j}≤10^6），其中w_{i,j}表示顶点i和j之间边的权重（如果i和j之间没有边，则w_{i,j}=0）。 输入的额外限制条件： - 对于每个i∈[1, n]，w_{i,i}=0； - 对于每对整数(i, j)，其中i∈[1, n]和j∈[1, n]，w_{i,j}=w_{j,i}； - 给定的图是连通的。 输出： 打印一个整数，即给定图的最小成本生成树的成本。 示例： 输入： 4 10 0 1 8 0 1 0 1 0 8 1 0 2 0 0 2 0 输出： 21 输入： 4 5 0 1 8 0 1 0 1 0 8 1 0 2 0 0 2 0 输出： 14 注意： 在第一个示例中，最小成本生成树由边(1, 3), (2, 3)和(3, 4)组成。其最大匹配为1。 在第二个示例中，最小成本生成树由边(1, 2), (2, 3)和(3, 4)组成。其最大匹配为2。