題目鏈接：點我點我:-) —只有洛谷有此題

題目描述： 奶酪店里最近出現(xiàn)了m只老鼠！它們的目標就是把生產出來的所有奶酪都吃掉。奶酪店中一天會生產n塊奶酪，其中第i塊的大小為pi，會在第ri秒被生產出來，并且必須在第di秒之前將它吃掉。第j只老鼠吃奶酪的速度為sj，因此如果它單獨吃完第i快奶酪所需的時間為pi/sj。老鼠們吃奶酪的習慣很獨特，具體來說： (1) 在任一時刻，一只老鼠最多可以吃一塊奶酪； (2) 在任一時刻，一塊奶酪最多被一只老鼠吃。 由于奶酪的保質期常常很短，為了將它們全部吃掉，老鼠們需要使用一種神奇的魔法來延長奶酪的保質期。將奶酪的保質期延長T秒是指所有的奶酪的di變成di+T。同時，使用魔法的代價很高，因此老鼠們希望找到最小的T使得可以吃掉所有的奶酪。

輸入格式： 輸入文件的第一行包含一個整數(shù)K，表示輸入文件中數(shù)據(jù)的組數(shù)。 每組數(shù)據(jù)的第一行包含兩個整數(shù)n和m，分別表示奶酪和老鼠的數(shù)量。接下來的n行每行包含三個整數(shù)pi,ri,di。最后m行每行包含一個整數(shù)，表示sj。pi,ri,di,sj的含義如上文所述。

輸出格式： 包含K行，每行包含一個實數(shù)，表示你找到的最小的T。你的答案和標準答案的絕對誤差不應超過10?4$10^{-4}$。

數(shù)據(jù)規(guī)模： 30%的數(shù)據(jù)中，1≤n,m≤5； 100%的數(shù)據(jù)中，1≤K≤5,1≤n,m≤30,1≤pi≤105$10^5$, 0 ≤ri < di≤107$10^7$,1≤sj≤105$10^5$。

思路： 網(wǎng)絡流好題 應該容易想到二分答案和離散化奶酪的時間點

先考慮樸素的建圖，也就是不考慮每個時刻可以有多只老鼠在不同的小時刻吃同一個奶酪 1.我們將源點每個奶酪鏈流量為p[i]的邊 2.然后把每只老鼠的每個時間段拆為一個點，再將其與對應的奶酪連邊，流量為這只老鼠可以在這個時間段吃多少奶酪 3.所有的老鼠向匯點連邊，無限流量

然而題目有限制，每個時刻可以有多只老鼠在不同的小時刻吃同一個奶酪，做法很巧妙，我們可以對老鼠的速度再進行拆點，把s[]從大到小排序然后與下一個作差，如”9 6 2 1” -> “3 4 1 1”，然后再將其與匯點連邊的流量改為（rat為老鼠編號，dur為時間段大小，s為作差后的數(shù)組）rat*s[rat]*dur即可

為什么呢？ 可以發(fā)現(xiàn)速度進行過如此處理之后， 9 = 3+4+1+1 6 = 4+1+1 2 = 1+1 1 = 1 9+6+2+1 = 3*1 + 4*2 + 1*3 + 1*4 (下面所有的s數(shù)組均為作差后的數(shù)組) 1.所以，當我們把老鼠點到匯點的流量限制設為rat*s[rat]*dur后，對于每一只老鼠，它‘吃’的量不超過實際可以‘吃’的量。（上述式子解釋了，實際包括編號比它小的老鼠的吃的量） 2.每個老鼠點與奶酪的連邊為s[rat]*dur，這樣可以保證每只老鼠實際不可以超過自己這段時間可以吃的奶酪。 3.（對于第2點的解釋）實際這段時間奶酪被吃的量不超過最快的老鼠的速度在這個時間段可以吃的量，如果每只老鼠在2點所述的邊滿流，那么實際相當于吃的最快的老鼠吃了這一整個時間段。而任何其它的情況均可以用別的老鼠湊出來，且由于第一點不會不合法

最后，每次二分答案，重新構圖跑最大流，檢查是否滿流即可。

感想： 很好的網(wǎng)絡流題目，然而連網(wǎng)絡流都沒想到是什么鬼？？？ 原來網(wǎng)絡流構圖還可以這么神奇，把每個點使勁拆成這個鬼樣子！！！ 網(wǎng)絡流的代碼應該沒什么問題了，但是構圖能力還要再提高啦！ 吐槽一下我調了3個小時的錯誤： 1.精度eps，寫錯居然可以導致最大流超過了我的p數(shù)組值的和！！！ 2.我的天哪：(f=dfs(e.to, fmin(Mint, e.cap-e.flow)))>eps 這句話我不小心把 > eps寫到最后一個括號里面了。。

代碼：