最大流題1.png
圖中括號(hào)外的數(shù)字代表允許容量，括號(hào)內(nèi)的數(shù)字代表了實(shí)際流量。
解法步驟：
（1）在已知可行流基礎(chǔ)上，通過標(biāo)號(hào)尋找增廣鏈。
正向?qū)ふ曳秋柡突。魺o正向，尋找反向非0弧。
image.png
（2）修改增廣鏈上的流量，非增廣鏈的流量不變，得到新的可行流。（調(diào)整量取最小值）
上圖中看到調(diào)整量 [6，2，2]中最小的是2。
（3）調(diào)整后，擦除原標(biāo)記，重新搜尋增廣鏈。
image.png
（4）重新搜尋增廣鏈。
image.png
調(diào)整量[4，1，1，1]最小是1，所以調(diào)整后得到
image.png
（5）之后不斷尋找后，直到無法標(biāo)號(hào)，即不存在增廣鏈，此可行流就為最大流，此處為14。
image.png
從s開始還能往下尋找非飽和的節(jié)點(diǎn)，歸為和s一個(gè)集合。
看另一個(gè)例題：
image.png
尋找增廣鏈，即不斷尋找正向（流出）非飽和邊，如果沒有的話看是否有逆向（流進(jìn)）非0邊。
逆向邊修改流量的時(shí)候減少之。
image.png
v1到v5這個(gè)逆向邊最多減少3個(gè)單位流量。
修改后：
繼續(xù)尋找增廣鏈：
image.png
最大流 W = 5 + 4 + 2 = 11
最小割集 {(Vs, V1), (Vs, V2), (Vs, V6)}
