#P51869. 「ICPC World Finals 2017」小小水管工 Son of Pipe Stream

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

题目描述

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

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

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

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

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

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

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

输入格式

第一行包含地点的数量 nn (3n200)(3 \leq n \leq 200),管道的数量 pp (n1p12n(n1))(n - 1 \leq p \leq \frac{1}{2}n(n-1)),实数值 vv (1v10)(1 \leq v \leq 10)aa (0.01a0.99)(0.01 \leq a \leq 0.99)。地点从 11nn 标号, Flubber 工厂是 11,水源是 22,FD 是 33。实数值在小数点后最多有 1010 位数字。

接下来 pp 行,每行描述一条管道。每行包含两个整数 jjkk (1j<kn)(1 \leq j < k \leq n),对应管道连接的两个地点,以及一个整数 cc (1c10)(1 \leq c \leq 10),对应管道的容量(单位:升/秒)。

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

输出格式

首先,对于每条管道(按输入的顺序),输出两个值:Flubber 在其中的流速和水在其中的流速(如果是从 kk 流到 jj ,则用负数表示),使得 FaW1aF^a \cdot W^{1 - a} 最大。然后,输出这个最大值,精确到绝对误差不超过 10410^{-4}

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

样例 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
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