Every time itrains on Farmer John's fields, a pond forms over Bessie's favorite cloverpatch. This means that the clover is covered by water for awhile and takesquite a long time to regrow. Thus, Farmer John has built a set of drainageditches so that Bessie's clover patch is never covered in water. Instead, thewater is drained to a nearby stream. Being an ace engineer, Farmer John hasalso installed regulators at the beginning of each ditch, so he can control atwhat rate water flows into that ditch.
Farmer John knows not only how many gallons of water each ditch can transportper minute but also the exact layout of the ditches, which feed out of the pondand into each other and stream in a potentially complex network.
Given all this information, determine the maximum rate at which water can betransported out of the pond and into the stream. For any given ditch, waterflows in only one direction, but there might be a way that water can flow in acircle.
The input includesseveral cases. For each case, the first line contains twospace-separated integers, N (0 <= N <= 200) and M (2 <= M <= 200).N is the number of ditches that Farmer John has dug. M is the number of intersectionspoints for those ditches. Intersection 1 is the pond. Intersection point M isthe stream. Each of the following N lines contains three integers, Si, Ei, andCi. Si and Ei (1 <= Si, Ei <= M) designate the intersections betweenwhich this ditch flows. Water will flow through this ditch from Si to Ei. Ci (0<= Ci <= 10,000,000) is the maximum rate at which water will flow throughthe ditch.
For each case,output a single integer, the maximum rate at which water may emptied from thepond.
Pahom on Water isan interactive computer game inspired by a short story of Leo Tolstoy about apoor man who, in his lust for land, forfeits everything. The game's startingscreen displays a number of circular pads painted with colours from the visiblelight spectrum. More than one pad may be painted with the same colour (definedby a certain frequency) except for the two colours red and violet. The displaycontains only one red pad (the lowest frequency of 400 THz) and one violet pad(the highest frequency of 789 THz). A pad may intersect, or even containanother pad with a different colour but never merely touch its boundary. Thedisplay also shows a figure representing Pahom standing on the red pad.
The game's objective is to walk the figure of Pahom from the red pad to theviolet pad and return back to the red pad. The walk must observe the followingrules:
1.If pad α and pad β have a common intersection and the frequency of the colourof pad α is strictly smaller than the frequency of the colour of pad β, thenPahom figure can walk from α to β during the walk from the red pad to theviolet pad
2. If pad α and pad β have a common intersection and the frequency of thecolour of pad α is strictly greater than the frequency of the colour of pad β,then Pahom figure can walk from α to β during the walk from the violet pad tothe red pad
3. A coloured pad, with the exception of the red pad, disappears from displaywhen the Pahom figure walks away from it.
The developer of the game has programmed all the whizzbang features of thegame. All that is left is to ensure that Pahom has a chance to succeed in eachinstance of the game (that is, there is at least one valid walk from the redpad to the violet pad and then back again to the red pad.) Your task is towrite a program to check whether at least one valid path exists in eachinstance of the game.
The input startswith an integer K (1 <= K <= 50) indicating the number of scenarios on aline by itself. The description for each scenario starts with an integer N (2<= N <= 300) indicating the number of pads, on a line by itself, followedby N lines that describe the colors, locations and sizes of the N pads. Eachline contains the frequency, followed by the x- and y-coordinates of the pad'scenter and then the radius. The frequency is given as a real value with no morethan three decimal places. The coordinates and radius are given, in meters, asintegers. All values are separated by a single space. All integer values are inthe range of -10,000 to 10,000 inclusive. In each scenario, all frequencies arein the range of 400.0 to 789.0 inclusive. Exactly one pad will have a frequencyof “400.0” and exactly one pad will have a frequency of “789.0”.
The output foreach scenario consists of a single line that contains: Game is VALID, or Gameis NOT VALID