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'(不然可能将原来不是割点的点变成割点)