Connection Status:
Competition Arena > AllGraphCuts

AllGraphCuts

SRM 687 · 2016-04-01 · by lg5293

SRM 687 · 2016-04-01 · by lg5293 · Graph Theory
Class Name: AllGraphCuts
Return Type: int[]
Method Name: findGraph
Arg Types: (vector<int>)
Problem Statement

Problem Statement

All graphs in this problem statement are simple undirected graphs with nonnegative integer edge weights. Here, "simple" means that there are no self-loops and each pair of vertices is connected by at most one direct edge.

Given a connected graph G, a cut between vertices i and j is a set E of edges such that each path from i to j contains at least one edge from the set E. In other words, if you cut all edges in E, the vertices i and j will end in different connected components.

If E is a set of edges, the weight of E is the sum of weights of edges it contains. For any distinct vertices i and j, the min cut weight between i and j is the minimum weight of a cut between i and j. Additionally, for any vertex i we define that the min cut weight between i and i is 0.

You are given a int[] x with n*n elements. You would like to find a connected graph G with n vertices, labeled 0 through n-1. The graph G must have the following properties:

  1. For each i and j, the min cut weight between vertices i and j must be exactly x[i*n+j].
  2. G must have at most 1000 edges.
  3. The weight of each edge must be between 0 and 10^5, inclusive.
For the given constraints it is guaranteed that whenever there is a graph that has the first property, there is a graph that has all three properties.

If there are no solutions, return the int[] {-1}. Otherwise, find any graph G that has the required properties and return a int[] with exactly m elements, where m is the number of edges in G. If G contains an edge (i,j) with weight w, the return value should contain the number (w*n*n + i*n + j).

Constraints

  • n will be between 2 and 50, inclusive.
  • x will have exactly n*n elements.
  • Each element of x will be between 0 and 10^5, inclusive.
Examples
0)
{0,1,
 1,0}
Returns: {6 }

In this case n = 2. The output can be decoded as a single edge between nodes 0 and 1 with weight 1 (i.e. 1*2*2 + 1*2 + 0 = 6).

1)
{0,1,
 1,1}
Returns: {-1 }

Note that since we have x[1*2+1] != 0, there is no valid solution.

2)
{0,2,2,
 2,0,2,
 2,2,0}
Returns: {10, 11, 14 }

This graph can be decoded as a triangle graph, where all the edge weights are 1.

3)
{0,1,2,3,4,
 1,0,2,3,4,
 1,2,0,3,4,
 1,2,3,0,4,
 1,2,3,4,0}
Returns: {-1 }
4)
{0,0,0,0}
Returns: {2 }

Note that some edge weights can be zero. The empty int[] {} is not a correct return value, since the graph G you return must be connected.

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

Coding Area

Language: C++17 · define a public class AllGraphCuts with a public method vector<int> findGraph(vector<int> x) · 130 test cases · 2 s / 256 MB per case

Submitting as anonymous