POJ 1815 Friendship

Posted on 2012-05-06 02:55 lenohoo 阅读(117) 评论(0)  编辑 收藏 引用

将s看成源点,t看成汇点,有结论:源点到汇点的最小点割集的大小等于图中最多的点不相交路径数目

做法:将每个点拆成两个点u和u',之间连容量为1的边,原来从u到v的边,变成从u'到v的边,边容量都是无穷大,新源点为s',新汇点还是t

这样,就将点不相交问题转化成边不相交问题,每条点不相交路径和一条边不相交路径一一对应

当有流值v时,意味着有v条边不相交路径(容量为1的限制),任意割的容量p>=v,每条边不相交路径中必有一条边是割边,当割是最小割

时,p=v,v为最大流,这时,最小点割集的大小就是最小边割集的大小也就是最大流

于是,当源点和汇点不直接相连的情况下,我们就得到了我们的第一个答案

但是题目要求很高,需要输出分数最小的点割集,即按字典序排序最小,我们可以贪心地从最小标号的顶点到最大标号的顶点一次枚举,每次删

除边i和i',如果新的最大流比原来的最大流小,说明该点在最小点割集中,否则,恢复边i和i'(不然可能将原来不是割点的点变成割点)

 


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


posts - 3, comments - 1, trackbacks - 0, articles - 16

Copyright © lenohoo