Berland Traffic

题意翻译

给定一张 $n$ 点 $m$ 边的无向的网络流，源点为 $1$，汇点为 $n$。 第 $i$ 条边用**有序**数对 $(a_i,b_i) (a_i\not= b_i)$ 和容量值 $c_i$ 描述，表示连接 $a_i$ 与 $b_i$，容量为 $c_i$。 你应当给这条边赋一个实数流量 $x_i$，满足 $|x_i|\le c_i$，如果是正的表示从 $a_i$ 流向 $b_i$ 大小为 $x_i$，否则表示从 $b_i$ 流向 $a_i$ 大小为 $-x_i$。 你构造的流需要满足： - 流守恒。即对所有不为 $1$ 或 $n$ 的点 $u$，进入 $u$ 的流等于从 $u$ 出去的流。 - 对任意两个连通的节点 $x,y$，从 $x$ 到 $y$ 的所有路径 $x_i$（流量）的和都是相等的。 现在请输出最大流（可以理解为 $\sum_v x_{1,v}$），并构造一个方案。

题目描述

Berland traffic is very different from traffic in other countries. The capital of Berland consists of $ n $ junctions and $ m $ roads. Each road connects a pair of junctions. There can be multiple roads between a pair of junctions. For each road we know its capacity: value $ c_{i} $ is the maximum number of cars that can drive along a road in any direction per a unit of time. For each road, the cars can drive along it in one of two direction. That it, the cars can't simultaneously move in both directions. A road's traffic is the number of cars that goes along it per a unit of time. For road ( $ a_{i},b_{i} $ ) this value is negative, if the traffic moves from $ b_{i} $ to $ a_{i} $ . A road's traffic can be a non-integer number. The capital has two special junctions — the entrance to the city (junction 1) and the exit from the city (junction $ n $ ). For all other junctions it is true that the traffic is not lost there. That is, for all junctions except for 1 and $ n $ the incoming traffic sum equals the outgoing traffic sum. Traffic has an unusual peculiarity in the capital of Berland — for any pair of junctions ( $ x,y $ ) the sum of traffics along any path from $ x $ to $ y $ doesn't change depending on the choice of the path. Such sum includes traffic along all roads on the path (possible with the "minus" sign, if the traffic along the road is directed against the direction of the road on the path from $ x $ to $ y $ ). Your task is to find the largest traffic that can pass trough the city per one unit of time as well as the corresponding traffic for each road.

输入输出格式

输入格式

The first line contains a positive integer $ n $ — the number of junctions ( $ 2<=n<=100 $ ). The second line contains integer $ m $ ( $ 1<=m<=5000 $ ) — the number of roads. Next $ m $ lines contain the roads' descriptions. Each road contains a group of three numbers $ a_{i} $ , $ b_{i} $ , $ c_{i} $ , where $ a_{i},b_{i} $ are the numbers of junctions, connected by the given road, and $ c_{i} $ ( $ 1<=a_{i},b_{i}<=n $ ; $ a_{i}≠b_{i} $ ; $ 0<=c_{i}<=10000 $ ) is the largest permissible traffic along this road.

输出格式

In the first line print the required largest traffic across the city. Then print $ m $ lines, on each line print the speed, at which the traffic moves along the corresponding road. If the direction doesn't match the order of the junctions, given in the input, then print the traffic with the minus sign. Print the numbers with accuracy of at least five digits after the decimal point. If there are many optimal solutions, print any of them.

输入输出样例

输入样例 #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

题意翻译

给定一张 $n$ 点 $m$ 边的无向的网络流，源点为 $1$，汇点为 $n$。 第 $i$ 条边用**有序**数对 $(a_i,b_i) (a_i\not= b_i)$ 和容量值 $c_i$ 描述，表示连接 $a_i$ 与 $b_i$，容量为 $c_i$。 你应当给这条边赋一个实数流量 $x_i$，满足 $|x_i|\le c_i$，如果是正的表示从 $a_i$ 流向 $b_i$ 大小为 $x_i$，否则表示从 $b_i$ 流向 $a_i$ 大小为 $-x_i$。 你构造的流需要满足： - 流守恒。即对所有不为 $1$ 或 $n$ 的点 $u$，进入 $u$ 的流等于从 $u$ 出去的流。 - 对任意两个连通的节点 $x,y$，从 $x$ 到 $y$ 的所有路径 $x_i$（流量）的和都是相等的。 现在请输出最大流（可以理解为 $\sum_v x_{1,v}$），并构造一个方案。