#P3597. [Scoi2014]方伯伯运椰子

    ID: 2804 传统题 1000ms 512MiB 尝试: 831 已通过: 377 难度: 8 上传者: 标签>难度分类提高+/省选-图论Karp 最小平均圈算法Tarjan 强连通分量算法动态规划滚动数组CF2500By佚名提供

[Scoi2014]方伯伯运椰子

[SCOI2014] 方伯伯运椰子

题目描述

四川的方伯伯为了致富,决定引进海南的椰子树。他的椰子园十分现代化,有一套独特的交通系统。

椰子园的运输网络是一张有向无环图,有 N+2N+2 个结点和 MM 条道路。入口是 N+1N+1 号结点,出口是 N+2N+2 号结点。每条道路从 uiu_i 指向 viv_i,当前容量为 cic_i,每运送一单位椰子花费 did_i。椰子园的交通系统早先由一位工程师优化过。初始方案中,每条道路的运输量恰好等于其容量。

与入口相连的道路只有一条。方伯伯担心改动它会使整个交通系统瘫痪,因此这条道路的容量固定。对其他道路,可以花费 aia_i 将容量减 11,也可以花费 bib_i 将容量增 11。道路容量不能降到负数。同一条道路可以调整多次,每次计作一次操作。

海南椰子将要大丰收,方伯伯担心运输费用过高,决定至少调整一次。调整后,所有道路仍须满负荷,每个中途结点的流入量仍等于流出量,从入口到出口的总运输量不得减少。

设初始运输费用为 XX,调整后的运输费用与调整费用之和为 YY,调整次数为 kk。求 (X−Y)/k(X-Y)/k 的最大值。

输入格式

第一行两个整数 N,MN,M。接下来 MM 行,每行六个整数 ui,vi,ai,bi,ci,diu_i,v_i,a_i,b_i,c_i,d_i,依次为道路起点、终点、减容一次的费用、增容一次的费用、原容量和单位运输费用。

输出格式

输出一行一个实数,保留两位小数。保证答案大于 00。

样例

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

数据范围

对于所有数据,1≤N≤5×1031\le N\le 5\times 10^3, M≤3×103M\le 3\times10^3, 1≤ui,vi≤N+21\le u_i,v_i\le N+2, 0≤ai,bi≤5000\le a_i,b_i\le 500, 0≤ci≤1040\le c_i\le 10^4, 0≤di≤1030\le d_i\le 10^3。