#P6938. [ICPC 2017 WF] Son of Pipe Stream

[ICPC 2017 WF] Son of Pipe Stream

题目描述

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 out-of-control 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/waterFlubber/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 vv , so a pipe that can transport vliters/secondv liters/second of water can transport only 1liter/second1 liter/second of Flubber. The pipe's capacity scales linearly for mixtures of the two. To be precise, if cc denotes the water capacity of the pipe and ff and ww are the rates of Flubber and water moving through the pipe (all measured in liters/second),liters/second), then the capacity constraint is given by the inequality vf+wcv · f + w \le 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: FaW1a,F^{a} · W^{1−a}, where FF is the rate of incoming Flubber in liters/second,Wliters/second, W is the rate of incoming water in liters/second,liters/second, and a is a given constant between 00 and 11 .

Determine the maximum value of FaW1aF^{a} · W^{1−a} that can be achieved and how to route the Flubber and water to achieve it.

输入格式

The input starts with a line containing the number of locations n(3n200)n (3 \le n \le 200) , the number of pipes p(n1pp (n − 1 \le p \le n(n 1)/2)− 1)/2) , and the real values v(1v10)v (1 \le v \le 10) and a (00 . 0101 \le a 0 \le 0 . 9999) . Locations are numbered from 11 to nn ; 11 is the Flubber factory, 22 is the water source, and 33 is the FD. The real values have at most 1010 digits after the decimal point.

The following pp lines each describe one pipe. Each line contains two integers jj and k(1j<kn)k (1 \le j < k \le n) , giving the locations connected by the pipe, and an integer c(1c10)c (1 \le c \le 10) , giving the water capacity of the pipe in liters/second.liters/second.

No two pipes connect the same pair of locations. Furthermore, it is guaranteed that the network is connected.

输出格式

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 kk to j)j) , such that FaW1aF^{a} ·W^{1−a} is maximized. Then display that maximum value accurate to within an absolute error of 104.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 104.10^{−4}.

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

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

提示

Time limit: 5 s, Memory limit: 512 MB.