在"最后的residual network"中，令S:{自S可到的点}, T:{自S不可到的点}
则(S,T)是"原本"flow network的min-cut (题目的图)
min-cut:(S,T)满足:
1. S∪T=V 且 S∩T={}
2. S->T的边的weight和为所有cut中最小
我想你说的"min-cut值"，应该是第2点提到的weight和，
因为max flow的值会被所有cut的值给限制，又min-cut的值是所有cut中最小的，
所以max flow值就会等于min-cut的值 (cormen p723)
以交大这题为例，min-cut为S={S,C},T={A,B,D,T} (因为S只能走到C)
max flow为5，原本的图S->T的边有(S,A)和(C,D)它们的weight加总为2+3=5
※ 引述《qoojordon (颖川琦)》之铭言：
: 出处:交大资联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
: 会比较小但不一定会相等 , 我是不是误解了什么@@"

取这组的话也会cut到(A,C)和(B,C),它们不用算进去是因为没有flow流过吗 ? 为什么(A,C)(B,C)没算进cut值?先谢谢你的回答~

楼上是跳针回两个一样吗XD结果电脑板是正常的囧，抱歉我想是不是因为min cut上的边必顺向满逆向空(A,C)(B,C)是逆向边

谢谢S大的想法,我想应该和你说的一样,逆向边不会贡献flow,所以求出来的cut恰巧不用算进容量的都是逆向边

定义的第2点，cormen是定义成cut的capacity，就是由S流向T的所有边之capacity总和

谢谢你~