Generalized Spanning Trees

All submissions for this problem are available.
A spanning tree of an undirected, connected graph (V,E) with vertex set V and edge set E is a subset of edges F such that the graph (V,F) is connected and has no cycles. After a few moments thought, one realizes that an equivalent way to say this is to say:
 1) F = V  1
 2) For any nonempty subset of nodes S, the number of edges with both endpoints in S is does not exceed S1.
There is a fairly simple algorithm that can determine if a set of edges F is indeed a spanning tree of a graph. Simply check that F = V  1 and that the graph (V,F) is connected using your favorite connectivity algorithm.
As in all topics in mathematics, the next step is to generalize what is known. So, consider the following generalization of spanning trees. Say a generalized spanning tree (GST) of a graph (V,E) is a function f from the set of edges E = {e_{1}, e_{2}, ..., e_{M}} to the real interval [0,1] such that the following conditions hold:
 1) f(e_{1}) + f(e_{2}) + ... + f(e_{M}) = V  1
 2) For any nonempty subset of nodes S, the sum of the f(e) values for edges e with both endpoints in S does not exceed S1.
One can see that this generalizes the notion of a spanning tree since spanning trees (in the classical sense) correspond to GSTs by setting f(e) = 1 if e is in the spanning tree and f(e) = 0 if e is not in the spanning tree.
Your task is to determine if a given function is a GST of a given graph.
Input:
The first line contains a single integer T (about 20) indicating the number of test cases to follow.
Each test case begins with two integers N and M where N is the number of nodes and M is the number of edges. The following M lines describe the edges, one per line. Each line contains three values u, v, f where 1 <= u, v <= n are the endpoints of the edge and f is a rational number between 0 and 1 (inclusive). This rational number is the value of the edge in the proposed GST.
The rational numbers are always presented as n/d (even if d=1) where both n and d are nonnegative and have no common factors.
The input graphs have no parallel edges or loops and are, of course, undirected. Consecutive cases will be separated by a blank line (including a blank line preceding the first case).
Bounds: 2 <= N <= 50, 1 <= M <= 100, and no denominator of any fraction in the input exceeds 30.
Output:
If the function is a GST, you are to simply print a single line saying "GST".
If the first constraint (the sum of the values of all edges is N1) is violated, then you should print a single line displaying just the number 1.
Otherwise, if constraint 1) holds but constraint 2) is violated for some nonempty set S, you should print three lines. The first line simply contains the integer 2. The second contains the size of a nonempty
subset of the nodes whose corresponding constraint is violated. The third line lists the nodes (in any order) that are part of such a set with a violated constraint (the number of nodes is as reported in the second line).
If there are multiple nonempty sets whose constraints are violated, then any will do. Print a blank line after the output for each case.
Example:
Input:
3 3 3 1 2 2/3 2 3 2/3 3 1 2/3 3 3 1 2 1/1 2 3 1/1 3 1 1/1 4 6 1 2 1/5 1 3 1/5 1 4 1/5 2 3 4/5 2 4 4/5 3 4 4/5
Output:
GST 1 2 3 2 3 4
Author:  friggstad 
Tester:  keshav_57 
Editorial  http://discuss.codechef.com/problems/GST 
Tags  friggstad, hard, may10 
Date Added:  10042010 
Time Limit:  1.07916 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, CS2, PAS fpc, PAS gpc, RUBY, PHP, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TEXT 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions