判断最小割是否唯一

来源:学生作业帮助网 编辑:作业帮 时间:2024/04/29 06:11:16
判断最小割是否唯一

判断最小割是否唯一
判断最小割是否唯一

判断最小割是否唯一
ZOJ 2587 是一道判断最小割是否唯一的题目.
我们都知道最小割等于最大流,可是这只是数值上有答案了呀,这唯一性可怎么办?一样是通过最大流来判断!
步骤:
1、我们先对原图求一次最大流
2、对残留网络,我们从S开始,找到所有所有S能到达的点;再从T开始,找出所有能到达T的点.
3、判断原网络中是否还有没有访问到的点,如果没有,则唯一,否者,不唯一!