剛開(kāi)始做的時(shí)候狂RE啊，還以為是自己的SPFA有問(wèn)題，檢查了很長(zhǎng)時(shí)間...
更為神跡的是，System 居然返回一個(gè)我從來(lái)沒(méi)有看到過(guò)的結(jié)果，囧~
做法是 先把所有的區(qū)間離散化 ，也就是只留端點(diǎn)，然后排序，去重，標(biāo)號(hào)。
增加超級(jí)源超級(jí)匯s,t.
假設(shè)剩下n個(gè)點(diǎn)， 加上超級(jí)源超級(jí)匯是n+2個(gè)。超級(jí)源為0,匯為n+1.
從0開(kāi)始，順序建一條流量為k,費(fèi)用為0的邊，將所有點(diǎn)串起來(lái)。然后再根據(jù)所輸入邊的信息，找到對(duì)應(yīng)點(diǎn)的位置，連一條流量是1，費(fèi)用是-w的邊，最后從s到t做最小費(fèi)用。
比如說(shuō)
3 1
1 3 2
2 3 4
3 4 8
將 1，3，2，3，3，4排序
變成 1 2 3 3 3 4
去重 1 2 3 4
然后 0->1 1->2 2->3 3->4 4->5 建邊
再 1->3 2->3 3->4 建邊 即可
注意這里只是數(shù)字剛好和位置相同 實(shí)際應(yīng)該用位置信息連邊 這個(gè)做過(guò)網(wǎng)絡(luò)流的都知道吧 ，最后Minflow即可。
不過(guò)我還沒(méi)有想明白為什么可以這樣做，它的正確性如何證明呢？