Connection Status:
Competition Arena > Revmatching

Revmatching

2015 TCO 1A · 2015-04-08 · by subscriber

2015 TCO 1A · 2015-04-08 · by subscriber · Brute Force, Graph Theory, Greedy
Class Name: Revmatching
Return Type: int
Method Name: smallest
Arg Types: (vector<string>)
Problem Statement

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.

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

Submissions are judged against all 76 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Revmatching with a public method int smallest(vector<string> A) · 76 test cases · 2 s / 256 MB per case

Submitting as anonymous