題目描述

四川的方伯伯為了致富，決定引進(jìn)海南的椰子樹。方伯伯的椰子園十分現(xiàn)代化，椰子園中有一套獨(dú)特的交通系統(tǒng)。

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

在這個(gè)交通網(wǎng)絡(luò)中，只有一條道路與起點(diǎn)相連。因?yàn)榕獕牧诉@條道路就會導(dǎo)致整個(gè)交通網(wǎng)絡(luò)癱瘓，聰明的方伯伯決定絕不對這條道路進(jìn)行調(diào)整，也就是說，現(xiàn)在除了這條道路之外，對其余道路都可以進(jìn)行調(diào)整。

有兩種調(diào)整方式：

一條道路可以被多次調(diào)整。

由于很久以前，方伯伯就請過一個(gè)工程師，對這個(gè)交通網(wǎng)絡(luò)進(jìn)行過一次大的優(yōu)化調(diào)整。所以現(xiàn)在所有的道路都被完全的利用起來了，即每條道路的負(fù)荷都是滿的（每條道路的流量等于其容量）。

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

設(shè)調(diào)整后的總費(fèi)用是 Y，調(diào)整之前的總費(fèi)用是 X。現(xiàn)在方伯伯想知道，最優(yōu)調(diào)整比率是多少，即假設(shè)他進(jìn)行了 k 次調(diào)整，(X - Y)/k最大能是多少？

注：總費(fèi)用 = 交通網(wǎng)絡(luò)的運(yùn)輸花費(fèi) + 調(diào)整的花費(fèi) 輸入輸出格式 輸入格式：

第一行包含二個(gè)整數(shù)N，M接下來M行代表M條邊，表示這個(gè)交通網(wǎng)絡(luò)每行六個(gè)整數(shù)，表示Ui,Vi,Ai,Bi,Ci,Di接下來一行包含一條邊，表示連接起點(diǎn)的邊

輸出格式：

一個(gè)浮點(diǎn)數(shù)，保留二位小數(shù)。表示答案，數(shù)據(jù)保證答案大于0

分析： 1.因?yàn)楸绢}要求的是分?jǐn)?shù)的最大值，所以要用到分?jǐn)?shù)規(guī)劃 2.因?yàn)榕c源點(diǎn)相連的只有一條邊，所以這個(gè)圖的流量是守恒的（總量不會變化） 3.那么壓縮相當(dāng)于退流，擴(kuò)容相當(dāng)于增廣，增廣相當(dāng)于加了一條。 4.擴(kuò)容1的費(fèi)用為b+d,壓縮1的費(fèi)用為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即是擴(kuò)容的費(fèi)用加上壓縮的費(fèi)用。由于最后要除上操作總數(shù)k，因此對于相同的邊操作多次是沒有意義的。又因?yàn)榇嬖趍id的影響，所以每次加上mid再判斷是否有負(fù)權(quán)環(huán)即可。