Revmatching

Problem Source

TCO 2015 Round 1A Hard

Problem Description

Given a complete bipartite graph with $n$ vertices on each side, every edge has a weight. Find a set of edges with minimum total weight such that, after deleting this set of edges, there is no perfect matching.

Input Format

The first line contains one integer $n (n\leq 20)$, the number of vertices.

The following $n$ lines each contain $n$ integers, representing the weight of each edge. The edge weights are guaranteed to be between $1$ and $10000$.

Output Format

Output one number: the answer.

Sample Input

3
1 2 3
2 3 1
3 1 2

Sample Output

6

Constraints

$n\leq 20$; edge weights in $[1, 10000]$.

Hint

• A perfect matching exists iff Hall's condition holds. The minimum-weight edge set whose removal destroys all perfect matchings can be found via a minimum cut on an appropriate flow network (equivalently, a maximum-weight perfect matching on the complement weights).