題目描述

四川的方伯伯為了致富，決定引進海南的椰子樹。方伯伯的椰子園十分現代化，椰子園中有一套獨特的交通系統。

現在用點來表示交通節點，邊來表示道路。這樣，方伯伯的椰子園就可以看作一個有 n + 2 個交通節點，m條邊的有向無環圖。n +1 號點為入口，n +2 號點為出口。每條道路都有 6 個參數，ui，vi，ai，bi，ci，di，分別表示，該道路從 ui 號點通向 vi 號點，將它的容量壓縮一次要 ai 的花費，容量擴大一次要 bi 的花費，該條道路當前的運輸容量上限為 ci，并且每單位運輸量通過該道路要 di 的費用。

在這個交通網絡中，只有一條道路與起點相連。因為弄壞了這條道路就會導致整個交通網絡癱瘓，聰明的方伯伯決定絕不對這條道路進行調整，也就是說，現在除了這條道路之外，對其余道路都可以進行調整。

有兩種調整方式：

一條道路可以被多次調整。

由于很久以前，方伯伯就請過一個工程師，對這個交通網絡進行過一次大的優化調整。所以現在所有的道路都被完全的利用起來了，即每條道路的負荷都是滿的（每條道路的流量等于其容量）。

但方伯伯一想到自己的海南椰子會大豐收，就十分擔心巨大的運輸量下，會導致過多的花費。因此，方伯伯決定至少進行一次調整，調整之后，必須要保持每條道路滿負荷，且總交通量不會減少。

設調整后的總費用是 Y，調整之前的總費用是 X。現在方伯伯想知道，最優調整比率是多少，即假設他進行了 k 次調整，(X - Y)/k最大能是多少？

注：總費用 = 交通網絡的運輸花費 + 調整的花費 輸入輸出格式 輸入格式：

第一行包含二個整數N，M接下來M行代表M條邊，表示這個交通網絡每行六個整數，表示Ui,Vi,Ai,Bi,Ci,Di接下來一行包含一條邊，表示連接起點的邊

輸出格式：

一個浮點數，保留二位小數。表示答案，數據保證答案大于0

分析： 1.因為本題要求的是分數的最大值，所以要用到分數規劃 2.因為與源點相連的只有一條邊，所以這個圖的流量是守恒的（總量不會變化） 3.那么壓縮相當于退流，擴容相當于增廣，增廣相當于加了一條。 4.擴容1的費用為b+d,壓縮1的費用為a-d 5.化一下給的式子： x?yk>mid $$/frac{x-y}{k}>mid$$ x?y?k?mid>0 $$x-y-k*mid>0$$ y?x+k?mid<0 $$y-x+k*mid<0$$ y-x即是擴容的費用加上壓縮的費用。由于最后要除上操作總數k，因此對于相同的邊操作多次是沒有意義的。又因為存在mid的影響，所以每次加上mid再判斷是否有負權環即可。