我有以下問題掙扎（和解決實際）：檢查是否存在邊越過一些最小割
鑑於
G(V,E)，流網絡（容量爲整數），我們將表示最大流量f*。檢查邊緣e如果：
1.它穿過一些最小切割。
2.它穿過每個最小切割。
的溶液表明：
1減少邊緣e的容量，並檢查新的最大流量等於f*-1。如果是的話返回true。e的容量增加1並且如果最大流量增加則返回true。如果你能向我解釋這個算法背後有什麼想法，我會很高興。
由於
最大流最小切割定理指出，在一個流網絡，則流程從源到宿傳遞的最大數量是等於總在最小切割中邊緣的重量，即邊緣的最小總重量，如果被去除則將源與水槽斷開。
如果e確實跨越最小切割這意味着它是一組邊緣中的一個（我們稱之爲c_group）的是：如果從圖中移除
A），源並且接收器將不再連接（它們之間沒有路徑）
和B）它們的權重總和（我們稱之爲c_sum）是最小的（沒有滿足（A）的一組邊並且具有較小的總和）。
當我們「1的體重，從（A）我們知道c_group是切割，並從（B）我們現在c_sum是切口（其邊緣的總和的最小值」減少e在權重）該圖和現在的c_group的值當然是c_sum-1，因爲e在c_group中，我們將其重量減少了1。所以我們知道c_sum-1是圖中新的最小切割值（即使e屬於其他切割，它只能在切割中出現一次，因此它的重量減少意味着它所屬的每個切割減少了1，所以最小切割值不能超過1）。從最大流最小切割定理我們知道新的最小切割值意味着新的最大流量值是相同的（c_sum-1）。另一方面，如果e沒有穿過最小切割，那麼它所穿過的每個切割都不是最小的，這意味着組的權重總和大於最小切割的值。由於我們只有整數值權重，這意味着它們都比最小值大至少1，所以當我們將減少1時，每一次剪切就會減少到剪切前的最小剪切值或更高的值，這意味着最小值沒有被減少所改變，並且最大流量最小切割定理意味着最大流量沒有改變。
所以，現在我們知道，如果我們通過1減少e的價值，我們可以檢查最大流量值，如果它改變了（得到了由1減少），必須意味着e並越過最小切割。
我將進入更小細節，但是如果你仍然掙扎評論，我會擴大它還有：
當我們增加e的價值（這裏沒有多少關係）它會改變圖中切割的最小值，如果它是圖中每個最小切割的一部分。很顯然，它增加了它所屬的每個組的總和，並且如果存在構成最小切割的一組邊緣（在（1）中的條件（A）+（B）），那麼e不屬於然後增加其權重不會改變該組的權重總和，因此不會改變圖中切割的最小值。從最大流最小切割定理可以看出，如果圖的最小流量是圖中每個最小切割的一部分，則圖中的最大流量增加。
注：我在我在考慮組邊緣的切出考慮切爲假想線邊緣交叉之間的這個答案語言有點交替。這個混淆來自問題中引用問題的不相容語言和開始我的回答的引用定理。如果它讓任何人感到困惑，我很抱歉。基本上「切」在整個這個答案中指的是他們。