[Wf2017]Son of Pipe Stream

内存限制：512 MiB 时间限制：5 Sec

提交提交记录讨论

两年前,你在你的家乡协助安装了全国第一个Flubber管道网络并取得了巨大的成功。民意调查显示,每个人都喜欢

在自己的厨房里安装他们自己的Flubber分配器 (类似水龙头) ,现在有一些活跃的公民还发现了另一个用途。显然

Flubber与水混合后有助于扑灭火灾!这是一个非常及时的发现,因为最近失控的火灾真是意外地常见。你家乡的城

市委员会希望在中心车站生产Flubber和水的混合物来充分利用Flubber的这个特性。这个被称为Flubber Departme

nt (FD)的车站也将配备训练有素的专业人员,他们负责前往火灾场所并利用加工过的Flubber来控制火情。管道已

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

到FD的水。注意Flubber和水会流经相同的管道网络,甚至是同一个管道。所有管道都是双向的,但是Flubber和水不

能在相同的管道中以相反的方向运输。此外,如果两种液体在相同的管道以相同的方向输送,它们将不可避免地混合

。因此网络中的每个节点都配备了特殊的膜与过滤器,你可以根据自己的需要来分离和重组所有流进的混合物。网

络是一个封闭的系统,所以除了来源地和目的地(FD)之外,流入每个节点的总流速必须等于流出的总流速。每个管道

都有固定的容量。Flubber稍微粘稠一些,它具有粘度值v,这意味着可以运输v升/秒的水的管道只能运输1升/秒的Fl

ubber。而管道的容量对于两者的混合物是呈线性分布的。准确来说,如果用c表示管道相对水的容量限制,f和w表示

流经管道的Flubber和水的速率 (均以升/秒计算) ,则容量约束满足不等式v·f+w≤c。你主要关心的是制衡到达FD

的混合物。你希望液体总量尽可能多,但你也需要足够的水来稀释Flubber(未稀释时Flubber高度易燃) ,并且需要

足够的Flubber(毕竟是Flubber Department)!你已经想出了一个公式来衡量最终混合物的"价值":F^a·W^{1?a},其

中F是流入Flubber的速率,单位为升/秒,W 是流入水的速率,单位为升/秒,a是给定的0和1之间的常数。请你确定可

以得到的F^a·W^{1?a}最大值,以及如何安排Flubber和水来实现这个最大值。

第一行包含地点的数量n(3≤n≤200) ,管道的数量p(n?1≤p≤n(n?1)/2) ,实数值v(1≤v≤10)和a(0.01≤a≤0.99) 。

地点从1到n标号,Flubber工厂是1 ,水源是2 ,FD是3。实数值在小数点后最多有10位数字。

接下来p行,每行描述一条管道。每行包含两个整数j和k(1≤j<k≤n)

对应管道连接的两个地点,以及一个整数c(1≤c≤10),对应管道的容量(单位:升/秒) 。

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

首先,对于每条管道 (按输入的顺序) ,输出两个值:Flubber在其中的流速和水在其中的流速(如

果是从k流到j,用负数表示) ,使得F^a·W^{1?a}最大。然后,输出这个最大值,精确到绝对误差不超过10^-4。

如果存在多个解,那么任意一个解都是可接受的。

所有的限制 (不能在同一管道中以不同的方向输送Flubber和水、流量平衡、管道容量、构造解与答案的一致性)

必须满足绝对误差不超过10^-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

样例2

5 5 1.0 0.5

1 2 10

2 3 10

3 4 10

4 5 10

3 5 10

样例输出


			样例1

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

5 0

5 5

4.2 3.14159

4.2 3.14159

-4.2 -3.14159

5

#4957. [Wf2017]Son of Pipe Stream

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示