Problem1097--#2214. 「SCOI2014」方伯伯运椰子

1097: #2214. 「SCOI2014」方伯伯运椰子

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

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

现在用点来表示交通节点,边来表示道路。这样,方伯伯的椰子园就可以看作一个有 n+2n + 2n+2 个交通节点,mmm 条边的有向无环图。n+1n +1n+1 号点为入口,n+2n +2n+2 号点为出口。每条道路都有六个参数,ui,vi,ai,bi,ci,diu_i, v_i, a_i, b_i, c_i, d_iui,vi,ai,bi,ci,di,分别表示,该道路从 uiu_iui 号点通向 viv_ivi 号点,将它的容量压缩一次要 aia_iai 的花费,容量扩大一次要 bib_ibi 的花费,该条道路当前的运输容量上限为 cic_ici,并且每单位运输量通过该道路要 did_idi 的费用。

在这个交通网络中,只有一条道路与起点相连。因为弄坏了这条道路就会导致整个交通网络瘫痪,聪明的方伯伯决定绝不对这条道路进行调整,也就是说,现在除了这条道路之外,对其余道路都可以进行调整。

有两种调整方式:

  1. 选择一条道路,将其进行一次压缩,这条道路的容量会下降 1 单位。
  2. 选择一条道路,将其进行一次扩容,这条道路的容量会上升 1 单位。

一条道路可以被多次调整。

由于很久以前,方伯伯就请过一个工程师,对这个交通网络进行过一次大的优化调整。所以现在所有的道路都被完全的利用起来了,即每条道路的负荷都是满的(每条道路的流量等于其容量)。但方伯伯一想到自己的海南椰子会大丰收,就十分担心巨大的运输量下,会导致过多的花费。因此,方伯伯决定至少进行一次调整,调整之后,必须要保持每条道路满负荷,且总交通量不会减少。

设调整后的总费用是 YYY,调整之前的总费用是 XXX。现在方伯伯想知道,最优调整比率是多少,即假设他进行了 kkk 次调整,(X−Y)/k(X - Y)/k(XY)/k 最大能是多少?

注:总费用 = 交通网络的运输花费 + 调整的花费

输入格式

第一行包含两个整数 nnnmmm
接下来 mmm 行代表 mmm 条边,表示这个交通网络,每行六个整数,表示该条边的参数 Ui,Vi,Ai,Bi,Ci,DiU_i,V_i,A_i,B_i,C_i,D_iUi,Vi,Ai,Bi,Ci,Di

输出格式

一个浮点数,保留二位小数。表示答案,数据保证答案大于零。

样例

样例输入

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≤5000, 0≤M≤3000, 1≤Ui,Vi≤N+2, 0≤Ai,Bi≤500, 0≤Ci≤10000, 0≤Di≤10001 \leq N \leq 5000,\ 0 \leq M \leq 3000,\ 1 \leq U_i,V_i \leq N+2,\ 0 \leq A_i,B_i \leq 500,\ 0 \leq C_i \leq 10000,\ 0 \leq D_i \leq 10001N5000, 0M3000, 1Ui,ViN+2, 0Ai,Bi500, 0Ci10000, 0Di1000

Source/Category