题目描述

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/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 · 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: $F^{a} · W^{1−a},$ 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} · 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 (3 \le n \le 200)$ , the number of pipes $p (n − 1 \le p \le$ n(n $− 1)/2)$ , and the real values $v (1 \le v \le 10)$ and a ($0$ . $01 \le$ a $\le 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 \le j < k \le n)$ , giving the locations connected by the pipe, and an integer $c (1 \le c \le 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.

输出格式

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} ·W^{1−a}$ 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}.$

题目大意

题目描述

两年以前，你帮助你的家乡安装了国内的第一个 Flubber 管道网络，获得了巨大成功。投票表明每个人都喜欢在自己家的厨房里装上 Flubber 分配器，而现在一些有进取心的市民发现了一种新的用途——Flubber 和水混合后似乎可以帮助灭火！这是一个很及时的发现，因为最近无法控制的大火出奇地常见。

你家乡的市议会想在一个位于中央的地方制造 Flubber 和水的混合物以利用 Flubber 的这个属性。这个被称为 Flubber 部门的地方拥有专门训练的员工去往着火的地点并且利用经过处理的 Flubber 来控制火势。

管道已经在城市中铺设好。你会得到管道布局，而你需要决定如何将 Flubber 从 Flubber 工厂、将水从一个本地水源通过管道运送至 Flubber 部门。

注意 Flubber 和水会在同一管道网络中，甚至可能在同一条管道中流动。所有管道是双向的，但是 Flubber 和水不能在同一条管道中异向流动。此外，如果两种液体同向流过一条管道，它们会不可避免地混合，因此网络中的所有节点配备了特殊的膜和筛，如你所见，可以分离和重新组织所有流入的混合物。管道网络是个封闭系统，因此在每个节点处每种液体的总流入速率必须等于总流出速率，除了每种液体各自的源头和目的地（Flubber 部门）。

每条管道有某个容量，有些粘稠的 Flubber 有一个粘度值 v，所以能运输 v 升每秒的水的管道只能运输 1 升每秒的 Flubber。管道对于混合物的容量是线性变化的。更精确地，假设 c 表示管道对于水的容量，f 和 w 分别表示 Flubber 和水流过管道的速率（单位均为升每秒），则容量的限制用不等式 v⋅f+w≤c 表示。

你主要关心的是平衡流到 Flubber 部门的混合物。你想要尽可能多的混合液体，但是也需要足够的水——因为未经稀释的 Flubber 是高度易燃的——也需要足够的 Flubber——因为 Flubber 部门可不能没了 Flubber！你想出了一个公式来衡量最终混合物的价值：$F^a⋅W^{1−a}$，其中 F 是以升每秒为单位的 Flubber 的流入速率，W 是以升每秒为单位的水的流入速率，a 是一个给定的介于 0 和 1 之间的常数。

求出 $F^a⋅W^{1−a}$ 能达到的最大值以及如何安排 Flubber 和水的路径来达到它。

输入格式

输入的第一行包含地点的数量 n (3≤n≤300)，管道的数量 $p (n−1≤p≤\frac12n(n−1))$，和实数 v (1≤v≤10) 和 a (0.01≤a≤0.99)。地点从 1 到 n 标号；1 是 Flubber 工厂，2 是水源，3 是 Flutter 部门。实数的小数点后最多有十位。

接下来的 p 行每行描述了一条管道。每行有两个整数 j 和 k (1≤j<k≤n)，表示管道连接的地点，和一个整数 c (1≤c≤10)，表示这条管道的水容量，以升每秒为单位。

没有两条管道连接相同的两个地点，此外，还保证网络是连通的。

输出格式

首先，对于每条管道（按照输入的顺序），输出两个值：其中 Flubber 流过的速率和其中水流过的速率 （如果从 k 流到 j 则为负数），使得 $F^a⋅W^{1−a}$ 最大化。然后输出其最大值，在 $10^{−4}$ 的绝对误差以内。

如果有多解，输出任意一种均可。所有限制（Flubber 和水没有在同一条管道内异向流动、流量守恒、管道容量以及构造的解和其声称的值的一致性）需要在 $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.