判断最小割是否唯一

来源:学生作业帮助网 编辑:六六作业网 时间:2024/11/05 14:51:26
判断最小割是否唯一判断最小割是否唯一判断最小割是否唯一ZOJ2587是一道判断最小割是否唯一的题目.我们都知道最小割等于最大流,可是这只是数值上有答案了呀,这唯一性可怎么办?一样是通过最大流来判断!步

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

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