Son of Pipe Stream
题目描述
两年前,你在你的家乡协助安装了全国第一个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