All submissions for this problem are available.
The organizers of Radix TROIKA's , Robotic event, are preparing a track for the robot race. The outdoor nature of the track is a problem, as the weather isn't very pleasant. There is a chance of rain. Ankur and Geetanjali come up with a plan to keep water away from the track in case the rain gods decide to be cruel. Their main aim is to maximize water flow towards the pool, and minimize it to the track. They set up channels for the water to flow into a nearby pool. Some channels were of good quality, and some were of average quality. All amount of water could flow through the "good" channel, but only a certain amount of water could flow through the "average" one. Water always flowed from low to higher level.Given a network of such channels, determine the maximum amount of water that can flow to the pool. The water flows from level 1, and the pool is at level n.
First line of input is the number of test cases t . For each test case ,next line contains ‘n’ the number of levels and ‘Q’ the quantity of water allowed by average channels to pass through them . Next line contains an integer ‘m’ ., then m lines follow consisting of two integers and a character per line ie., ‘A’,’B’, the two levels between which a channel is present and third character ie., ‘M’ if channel is of average quality or ‘G’ if channel is of good quality.
Only one line per test case, the maximum lava that went to sea.
- 1 ≤ t ≤ 100
- 2 ≤ n ≤ 200
- 1 ≤ Q ≤ 100000
- 1 ≤ m ≤ 500
Input: 1 5 1 5 1 2 M 1 3 M 3 4 G 4 5 M 2 5 M Output: 2
|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.