MST with Matching
Contest: Educational Codeforces Round 163 (Rated for Div. 2)
Difficulty rating: 3100
Tags: bitmasks, brute force, dsu, graph matchings, trees

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.

Input format:
The 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.

Output format:
Print one integer — the minimum cost of a spanning tree of the given graph.

Constraints:
Time limit: 6.0 s
Memory limit: 512.0 MB

Note:
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$$$.

Example input:
4 10
0 1 8 0
1 0 1 0
8 1 0 2
0 0 2 0

Example output:
21

Example input:
4 5
0 1 8 0
1 0 1 0
8 1 0 2
0 0 2 0

Example output:
14

Editorial:
The key to solving this problem is applying Kőnig's theorem: in a bipartite graph, the size of the maximum matching is equal to the size of the minimum vertex cover. At the first glance it shouldn't work here, because our graph is not bipartite; however, when we leave only the edges belonging to the spanning tree we chose, it becomes bipartite. So instead of adding $$$c$$$ to the cost of the tree for each edge in its maximum matching, we can add $$$c$$$ to the cost of the tree for each vertex in its minimum vertex cover.
This allows us to try iterating on that vertex cover. Let's fix a set of vertices $$$S$$$, say that this is the minimum vertex cover, and the second part of the cost is equal to $$$c \cdot |S|$$$. How to build a minimum-cost spanning tree which has $$$S$$$ as its minimum vertex cover? Well, that's not really easy to do; but instead, we can build a minimum-cost spanning tree which has $$$S$$$ as one of its vertex covers (not necessarily minimum). The fact that there might be some other vertex cover of smaller size for the tree doesn't really matter, because we can generate this tree again using a smaller set of vertices as its vertex cover.
So, how do we build a minimum spanning tree such that $$$S$$$ is its vertex cover? This is actually easy: we forbid all edges such that none of their endpoints are in $$$S$$$ (because they can't be covered), and use any regular MST algorithm on all edges we have not forbidden. If we use Prim's algorithm, we get a solution in $$$O(2^n \cdot n^2)$$$, which is fast enough to pass the time limit. Kruskal's algorithm with DSU might be a bit slower, but can also get accepted.