「ICPC World Finals 2017」小小水管工 Son of Pipe Stream - Problem

题目描述

两年前，你在你的家乡协助安装了全国第一个 Flubber 管道网络并取得了巨大的成功。民意调查显示，每个人都喜欢在自己的厨房里安装他们自己的 Flubber 分配器（类似水龙头），现在有一些活跃的公民还发现了另一个用途。显然 Flubber 与水混合后有助于扑灭火灾！这是一个非常及时的发现，因为最近失控的火灾真是意外地常见。

你家乡的城市委员会希望在中心车站生产 Flubber 和水的混合物来充分利用 Flubber 的这个特性。这个被称为 Flubber Department（简称 FD）的车站也将配备训练有素的专业人员，他们负责前往火灾场所并利用加工过的 Flubber 来控制火情。

管道已经安置在整个城市之中。你需要通过管道的布局确定如何安排从 Flubber 工厂运送到 FD 的 Flubber 以及从当地水源到 FD 的水。

注意 Flubber 和水会流经相同的管道网络，甚至是同一个管道。所有管道都是双向的，但是 Flubber 和水不能在相同的管道中以相反的方向运输。此外，如果两种液体在相同的管道以相同的方向输送，它们将不可避免地混合。因此网络中的每个节点都配备了特殊的膜与过滤器，你可以根据自己的需要来分离和重组所有流进的混合物。网络是一个封闭的系统，所以除了来源地和目的地（FD）之外，流入每个节点的总流速必须等于流出的总流速。

每个管道都有固定的容量。 Flubber 稍微粘稠一些，它具有粘度值 $v$ ，这意味着可以运输 $v$ 升/秒的水的管道只能运输 $1$ 升/秒的 Flubber 。而管道的容量对于两者的混合物是呈线性分布的。准确来说，如果用 $c$ 表示管道相对水的容量限制，$f$ 和 $w$ 表示流经管道的 Flubber 和水的速率（均以升/秒计算），则容量约束满足不等式 $v \cdot f + w \leq c$。

你主要关心的是制衡到达 FD 的混合物。你希望液体总量尽可能多，但你也需要足够的水来稀释 Flubber（因为未稀释时 Flubber 高度易燃），并且需要足够的 Flubber（毕竟是 Flubber Department）！你已经想出了一个公式来衡量最终混合物的“价值”：$F^a \cdot W^{1 - a}$，其中 $F$ 是流入 Flubber 的速率，单位为升/秒，$W$ 是流入水的速率，单位为升/秒，$a$ 是给定的 $0$ 和 $1$ 之间的常数。

请你确定可以得到的 $F^a \cdot W^{1 - a}$ 最大值，以及如何安排 Flubber 和水来实现这个最大值。

输入格式

第一行包含地点的数量 $n$ $(3 \leq n \leq 200)$，管道的数量 $p$ $(n - 1 \leq p \leq \frac{1}{2}n(n-1))$，实数值 $v$ $(1 \leq v \leq 10)$ 和 $a$ $(0.01 \leq a \leq 0.99)$。地点从 $1$ 到 $n$ 标号， Flubber 工厂是 $1$，水源是 $2$，FD 是 $3$。实数值在小数点后最多有 $10$ 位数字。

接下来 $p$ 行，每行描述一条管道。每行包含两个整数 $j$ 和 $k$ $(1 \leq j < k \leq n)$，对应管道连接的两个地点，以及一个整数 $c$ $(1 \leq c \leq 10)$，对应管道的容量（单位：升/秒）。

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

输出格式

首先，对于每条管道（按输入的顺序），输出两个值：Flubber 在其中的流速和水在其中的流速（如果是从 $k$ 流到 $j$ ，则用负数表示），使得 $F^a \cdot W^{1 - a}$ 最大。然后，输出这个最大值，精确到绝对误差不超过 $10^{-4}$。

如果存在多个解，那么任意一个解都是可接受的。所有的限制（不能在同一管道中以不同的方向输送 Flubber 和水、流量平衡、管道容量以及构造解与答案的一致性）必须满足绝对误差不超过 $10^{-4}$。

样例 1

input

6 6 3.0 0.66
2 4 8
4 6 1
3 6 1
4 5 5
1 5 7
3 5 3

output

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

样例 2