PROBLEM STATEMENT
You have a weighted bipartite graph.
Each partition contains n vertices numbered 0 through n-1.
You are given the weights of all edges encoded into a vector A with n elements, each
containing n characters.
For each i and j, A[i][j] is '0' if there is no edge between vertex i in the first partition and
vertex j in the second partition.
Otherwise, A[i][j] is between '1' and '9', inclusive, and the digit represents the weight of the
corresponding edge.
A perfect matching is a permutation p of 0 through n-1 such that for each i there is an edge (of
any positive weight) between vertex i in the first partition and vertex p[i] in the second
partition.
Your goal is to have a graph that does not contain any perfect matching.
You are allowed to delete edges from your current graph.
You do not care about the number of edges you delete, only about their weights.
More precisely, you want to reach your goal by deleting a subset of edges with the smallest
possible total weight.
Compute and return the total weight of deleted edges in an optimal solution.
DEFINITION
Class:Revmatching
Method:smallest
Parameters:vector
Returns:int
Method signature:int smallest(vector A)
CONSTRAINTS
-A will contain exactly n elements.
-Each element in A will be n characters long.
-n will be between 1 and 20, inclusive.
-Each character in A will be between '0' and '9', inclusive.
EXAMPLES
0)
{"1"}
Returns: 1
There is a single edge. You have to delete it.
1)
{"0"}
Returns: 0
There are no edges and therefore there is no perfect matching.
2)
{"44","44"}
Returns: 8
3)
{"861","870","245"}
Returns: 6
4)
{"01000","30200","11102","10001","11001"}
Returns: 0
5)
{"0111101100","0001101001","1001001000","1000100001","0110011111","0011110100","1000001100","0001100000","1000100001","0101110010"}
Returns: 1