Connection Status:
Competition Arena > TreesCount

TreesCount

Member Single Round Match 474 · 2009-12-03 · by maksay

Member Single Round Match 474 · 2009-12-03 · by maksay · Dynamic Programming, Graph Theory
Class Name: TreesCount
Return Type: int
Method Name: count
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Little Dazdraperma likes graphs a lot. Recently she invented a new game for one person with graphs. She is given a connected undirected graph with N vertices numbered 0 to N-1, inclusive (see the notes for definitions of all unclear terms from graph theory). Each edge of the graph is labeled with a positive integer length. She tries to remove some edges (possibly 0) so that the resulting graph satisfies the following conditions:
  • The graph that remains is a tree with exactly N-1 edges.
  • For each v, 0 < v < N, the shortest distance between vertex 0 and vertex v is the same in the resulting graph and in the initial graph.
Dazdraperma wonders how many different resulting graphs that satisfy these conditions she can obtain. Two graphs are considered different if there are two different vertices such that one of the graphs contains an edge between these two vertices and another graph doesn't contain an edge between them.

You are given the representation of the initial graph as a String[] graph. This String[] contains exactly N elements and each element contains exactly N characters. The j-th character in the i-th element will be '0' if there is no edge between vertices i and j. Otherwise, it will be a character between '1' and '9' representing the length of the edge between vertices i and j.

Return the number of possible resulting graphs modulo 1000000007.

Notes

  • For the purpose of this problem, an undirected graph can be treated as a set of vertices and a set of edges, where each edge establishes a bidirectional connection between two different vertices.
  • A path between two different vertices A and B in a graph G is a sequence of 2 or more vertices v[0] = A, v[1], ..., v[L-1] = B, such that there's an edge in G between each two adjacent vertices in this sequence. A path is said to consist of edges between v[i] and v[i+1], where 0 ≤ i < L-1. The length of a path is the sum of lengths of all edges it consists of.
  • The path between vertices A and B in a graph G that has the minimum possible length is called the shortest path between them. The length of this path is called the shortest distance between A and B.
  • A graph G is connected if there's a path between each two different vertices of G.
  • A graph G is a tree if it is connected and contains exactly V-1 edges, where V is the total number of vertices in G.

Constraints

  • graph will contain between 2 and 50 elements, inclusive.
  • Each element of graph will contain the same number of characters as the number of elements in graph.
  • Each character in each element of graph will be between '0' and '9', inclusive.
  • For each i, the i-th character of i-th element of graph will always be '0'.
  • For each i and j, the i-th character of j-th element of graph will always be equal to the j-th character of i-th element of graph.
  • graph will represent a connected graph.
Examples
0)
{"01",
 "10"}
Returns: 1

The graph is already a tree, so the answer is 1.

1)
{"011",
 "101",
 "110"}
Returns: 1

The only possibility is to delete the edge between vertices 1 and 2.

2)
{"021",
 "201",
 "110"}
Returns: 2

You can either delete the edge between vertices 1 and 2 or the edge between vertices 0 and 1.

3)
{"0123",
 "1012",
 "2101",
 "3210"}
Returns: 6

More possibilities.

4)
{"073542",
 "705141",
 "350721",
 "517031",
 "442304",
 "211140"}
Returns: 2

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

Coding Area

Language: C++17 · define a public class TreesCount with a public method int count(vector<string> graph) · 109 test cases · 2 s / 256 MB per case

Submitting as anonymous