出处:交大资联103 12题
Q1-1:
一flow network 如下图 , 求min cut =?
3
A——→B 4
2↗｜ ／↑↘
S ｜1 ／3 ｜1 T
4↘↓↙ ｜↗3
C——→D
3
回头看以前没写完整的题目有不确定自己是否正确
做完FF Algo (flow)
2,3
2,2 A——→B 2,4
↗｜0,1 ／↑↘
S ｜ ／ ｜0,1T
3,4↘↓↙0,3 ｜↗
C——→D 3,3
3,3
我求出来的max flow =5
min cut=({S} , {A,B,C,D,T} ) 即切到的edge set为上图黄色标记
定理的max flow = min cut , min cut的值是怎么取的?
假设我min cut是取正确的 , 所以min cut代表的值 = 2+3 ? (是取cut上的flow加总?)
因为小黄书上写的cut值是"切集的容量" , 依这个定义取出来的值(2+4)只能保证max flow
会比较小但不一定会相等 , 我是不是误解了什么@@"