Two years ago, you helped install the nation’s very first
Flubber pipe network in your hometown, to great success. Polls
show that everyone loves having their own Flubber dispenser in
their kitchen, and now a few enterprising citizens have
discovered a use for it. Apparently Flubber, when mixed with
water, can help extinguish fires! This is a very timely
discovery, as outofcontrol fires have lately been
surprisingly common.
Your hometown’s city council would like to make use of this
property of Flubber by creating the Flubber/water mixture at a
centrally located station. This station, which is called the
Flubber Department (FD) will also have specialized employees
trained to travel to the locations of fires and make use of
their processed Flubber to control the blazes.
The pipes are already in place all around the city. You are
given a layout of the pipes, and must determine how to route
Flubber from the Flubber factory and water from a local source
through the pipes to the FD.
Note that both Flubber and water will be flowing through the
same network of pipes, perhaps even the same pipe. All pipes
are bidirectional, but Flubber and water cannot move in
opposite directions through the same pipe. Furthermore, if both
liquids are sent in the same direction through the same pipe,
they will inevitably mix. Therefore the nodes in the network
have been equipped with special membranes and filters that
enable you to separate and reorganize all incoming mixtures as
you see fit. The network is a closed system, so the total rate
of each fluid going into a node must equal the total rate of
that fluid going out, except at the source of that fluid and
the destination (the FD).
Each pipe has a certain capacity. Flubber, being somewhat
sluggish, has a viscosity value $v$, so a pipe that can transport
$v$ liters/second of water
can transport only $1$
liter/second of Flubber. The pipe’s capacity scales linearly
for mixtures of the two. To be precise, if $c$ denotes the water capacity of the
pipe and $f$ and
$w$ are the rates of
Flubber and water moving through the pipe (all measured in
liters/second), then the capacity constraint is given by the
inequality $v\cdot f + w \leq
c$.
Your main concern is balancing the mixture that reaches the
FD. You would like as much total liquid as possible, but you
also need a sufficient amount of water – because undiluted
Flubber is highly flammable – and a sufficient amount of
Flubber – because it would not be much of a “Flubber
Department” without Flubber! You have come up with a formula to
measure the “value” of the final mixture: $F^ a \cdot W^{1a}$, where
$F$ is the rate of
incoming Flubber in liters/second, $W$ is the rate of incoming water in
liters/second, and $a$ is
a given constant between $0$ and $1$.
Determine the maximum value of $F^ a \cdot W^{1a}$ that can be
achieved and how to route the Flubber and water to achieve
it.
Input
The input starts with a line containing the number of
locations $n$
($3 \leq n \leq 200$), the
number of pipes $p$
($n1 \leq p \leq \tfrac
{1}{2}n(n1)$), and the real values $v$ ($1
\leq v \leq 10$) and $a$ ($0.01 \leq a \leq 0.99$). Locations
are numbered from $1$ to
$n$; $1$ is the Flubber factory,
$2$ is the water source,
and $3$ is the FD. The
real values have at most $10$ digits after the decimal
point.
The following $p$ lines
each describe one pipe. Each line contains two integers
$j$ and $k$ ($1
\leq j < k \leq n$), giving the locations connected
by the pipe, and an integer $c$ ($1
\leq c \leq 10$), giving the water capacity of the pipe
in liters/second.
No two pipes connect the same pair of locations.
Furthermore, it is guaranteed that the network is
connected.
Output
First, for each pipe (in the order given in the input),
display two values: the rate of Flubber moving through it, and
the rate of water moving through it (negative if the liquid is
moving from $k$ to
$j$), such that
$F^ a \cdot W^{1a}$ is
maximized. Then display that maximum value accurate to within
an absolute error of $10^{4}$.
If there are multiple solutions, any one will be accepted.
All constraints (not sending Flubber and water in opposite
directions along the same pipe, flow conservation, pipe
capacities, and consistency between the constructed solution
and its claimed value) must be satisfied within an absolute
error of $10^{4}$.
Sample Input 1 
Sample Output 1 
6 6 3.0 0.66
2 4 8
4 6 1
3 6 1
4 5 5
1 5 7
3 5 3

0.000000000 1.360000000
0.000000000 1.000000000
0.000000000 1.000000000
0.000000000 0.360000000
0.880000000 0.000000000
0.880000000 0.360000000
1.02037965897

Sample Input 2 
Sample Output 2 
5 5 1.0 0.5
1 2 10
2 3 10
3 4 10
4 5 10
3 5 10

5 0
5 5
4.2 3.14159
4.2 3.14159
4.2 3.14159
5
