JOIN
Get Time

   Problem Statement  

 Problem Statement for Revmatching

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 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.

 

Definition

    
Class:Revmatching
Method:smallest
Parameters:String[]
Returns:int
Method signature:int smallest(String[] A)
(be sure your method is public)
    
 

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

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       2015 TopCoder Open Algorithm Round 1A - Division I, Level Three