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 vector graph. This vector
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.
DEFINITION
Class:TreesCount
Method:count
Parameters:vector
Returns:int
Method signature:int count(vector graph)
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
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.