The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 3680 Intervals 最小费用流 神迹一般的构图

刚开始做的时候狂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即可。

不过我还没有想明白为什么可以这样做,它的正确性如何证明呢?

posted on 2010-03-30 19:45 abilitytao 阅读(2069) 评论(1)  编辑 收藏 引用

评论

# re: POJ 3680 Intervals 最小费用流 神迹一般的构图 2014-11-14 01:51 Joker Poker

求教为什么会RE(ToT)  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理