Maximum Flow in a Special Graph
All submissions for this problem are available.
In this problem you are a given an un-directed graph containing N nodes numbered from 1 to N and M edges. Capacity of each edge will be given. For each (unordered) pair of nodes u and v, you need to find the maximum flow value from node u to v. Sum the answers for each pair u and v and print the sum. Note that the edges are undirected which means that fluid is allowed to flow in either direction but in a single direction at any point of time. Also flow value through an edge should not exceed its maximum capacity.
Given Graph has the following properties
- Graph contains exactly M = N-1 edges .
- From any node u to any node v, one can reach using the edges given. That means the graph is connected.
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains a single integer N denoting the number of nodes in the graph.
- Next M = N-1 lines follows. ith line contains three space separated integers ui, vi and ci respectively. Which means there is an edge between node ui and node vi having maximum capacity equal to ci.
- For each test case, output a single line containing the answer to the corresponding testcase. Answer to a testcase is sum of maximum flow value for each pair of nodes as described in the problem statement.
- 1 ≤ T ≤ 105
- 1 ≤ N ≤ 2 * 105
- sum of N over all the testcases will be ≤ 2 * 106
- 0 ≤ ci ≤ 4 * 108
- 1 ≤ u, v ≤ N
- u != v
Input: 1 4 1 2 3 2 3 2 2 4 5 Output: 17
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, 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, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.