Pseudoforest |
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) |
Total Submission(s): 402 Accepted Submission(s): 173 |
Problem DescriptionIn graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. The maximal pseudoforests of G are the pseudoforest subgraphs of G that are not contained within any larger pseudoforest of G. A pesudoforest is larger than another if and only if the total value of the edges is greater than another one’s. |
InputThe input consists of multiple test cases. The first line of each test case contains two integers, n(0 < n <= 10000), m(0 <= m <= 100000), which are the number of the vertexes and the number of the edges. The next m lines, each line consists of three integers, u, v, c, which means there is an edge with value c (0 < c <= 10000) between u and v. You can assume that there are no loop and no multiple edges. The last test case is followed by a line containing two zeros, which means the end of the input. |
OutputOutput the sum of the value of the edges of the maximum pesudoforest. |
Sample Input3 3 |
Sample Output3 // 找到一个图,使得每一个连通分量最多有一个环 |