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 String[] **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. |