刚开始做的时候狂RE啊,还以为是自己的SPFA有问题,检查了很长时间...
更为神迹的是,System 居然返回一个我从来没有看到过的结果,囧~
做法是 先把所有的区间离散化 ,也就是只留端点,然后排序,去重,标号。
增加超级源超级汇s,t.
假设剩下n个点, 加上超级源超级汇是n+2个。超级源为0,汇为n+1.
从0开始,顺序建一条流量为k,费用为0的边,将所有点串起来。然后再根据所输入边的信息,找到对应点的位置,连一条流量是1,费用是-w的边,最后从s到t做最小费用。
比如说
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 建边 即可
注意这里只是数字刚好和位置相同 实际应该用位置信息连边 这个做过网络流的都知道吧 ,最后Minflow即可。
不过我还没有想明白为什么可以这样做,它的正确性如何证明呢?