← 返回题目列表

Codeforces · 267/C

C. 贝尔兰交通

中文机器翻译题面 查看原题

伯兰的交通与其他国家的交通有很大不同。 Berland的首都由n个路口和m条道路组成。每条道路连接一对路口。一对路口之间可以有多条道路。对于每条道路,我们都知道其容量:ci 值是单位时间内可以沿道路任意方向行驶的最大汽车数量。对于每条道路,汽车可以沿两个方向之一行驶。也就是说,汽车不能同时向两个方向移动。道路的交通量是指单位时间内通过该道路的汽车数量。对于道路 (ai, bi),如果交通量从 bi 移动到 ai,则该值为负。道路的交通量可以是非整数。

首都有两个特殊的路口——城市入口(1号路口)和城市出口(n号路口)。对于所有其他路口,交通确实不会丢失。也就是说,对于除 1 和 n 之外的所有路口,传入流量总和等于传出流量总和。

Berland 首都的交通有一个不寻常的特点 - 对于任何一对路口 (x, y),从 x 到 y 的任何路径上的交通总和不会根据路径的选择而改变。该总和包括沿路径上所有道路的交通量(如果沿道路的交通量与从 x 到 y 的路径上的道路方向相反,则可能带有“减号”)。

你的任务是找出单位时间内可以通过城市的最大交通量以及每条道路对应的交通量。

输入

第一行包含一个正整数 n — 结点数量 (2 ≤ n ≤ 100)。第二行包含整数 m (1 ≤ m ≤ 5000) — 道路数量。接下来的 m 行包含道路的描述。每条道路包含一组三个数字 ai、bi、ci,其中 ai、bi 是给定道路连接的路口数量,ci (1 ≤ ai, bi ≤ n; ai ≠ bi; 0 ≤ ci ≤ 10000) 是该道路沿线的最大允许流量。

输出

在第一行打印所需的全市最大交通量。然后打印 m 行,每行打印交通沿着相应道路移动的速度。如果方向与输入中给定的路口顺序不匹配,则使用减号打印交通。打印数字,精确到小数点后至少五位数字。

如果有多个最优解,则打印其中任意一个。

示例

输入 #1

2
3
1 2 2
1 2 4
2 1 1000

输出 #1

6.00000
2.00000
2.00000
-2.00000

输入 #2

7
11
1 2 7
1 2 7
1 3 7
1 4 7
2 3 7
2 5 7
3 6 7
4 7 7
5 4 7
5 6 7
6 7 7

输出 #2

13.00000
2.00000
2.00000
3.00000
6.00000
1.00000
3.00000
4.00000
7.00000
1.00000
2.00000
6.00000