#P3597. [Scoi2014]方伯伯运椰子
[Scoi2014]方伯伯运椰子
[SCOI2014] 方伯伯运椰子
题目描述
四川的方伯伯为了致富,决定引进海南的椰子树。他的椰子园十分现代化,有一套独特的交通系统。
椰子园的运输网络是一张有向无环图,有 个结点和 条道路。入口是 号结点,出口是 号结点。每条道路从 指向 ,当前容量为 ,每运送一单位椰子花费 。椰子园的交通系统早先由一位工程师优化过。初始方案中,每条道路的运输量恰好等于其容量。
与入口相连的道路只有一条。方伯伯担心改动它会使整个交通系统瘫痪,因此这条道路的容量固定。对其他道路,可以花费 将容量减 ,也可以花费 将容量增 。道路容量不能降到负数。同一条道路可以调整多次,每次计作一次操作。
海南椰子将要大丰收,方伯伯担心运输费用过高,决定至少调整一次。调整后,所有道路仍须满负荷,每个中途结点的流入量仍等于流出量,从入口到出口的总运输量不得减少。
设初始运输费用为 ,调整后的运输费用与调整费用之和为 ,调整次数为 。求 的最大值。
输入格式
第一行两个整数 。接下来 行,每行六个整数 ,依次为道路起点、终点、减容一次的费用、增容一次的费用、原容量和单位运输费用。
输出格式
输出一行一个实数,保留两位小数。保证答案大于 。
样例
5 10
1 5 13 13 0 412
2 5 30 18 396 148
1 5 33 31 0 39
4 5 22 4 0 786
4 5 13 32 0 561
4 5 3 48 0 460
2 5 32 47 604 258
5 7 44 37 75 164
5 7 34 50 925 441
6 2 26 38 1000 22
103.00
数据范围
对于所有数据,, , , , , 。