P4126 [AHOI2009]最小割

https://www.cnblogs.com/dugudashen/p/6228304.html
求解一張有向圖中關(guān)于最小割的可行邊和必須邊，可行邊定義為存在一種最小割包含這條邊，必須邊定義為任意一種最小割包含這條邊。

可行邊的條件：

滿流

對于邊<u,v>不存在從u到v的增廣路

首先如果不滿流，那么一定存在一條滿流的權(quán)值更小的邊。
如果存在增廣路那么一定不可能是割邊，因為它并沒有割開點集。

必須邊的條件：

滿流

并且縮點之后<u,v>這條邊直接連接了S和T所在的連通塊

在縮點之后，如果S能夠到u，v能夠到T，那么一定存在最小割的可行邊可以替代這個邊，所以就不是必須邊了。

最小割必須邊的另一種理解是擴大容量后能夠增大最大流的邊。那么由于原圖已經(jīng)不存在增廣路，所以擴大容量后能夠增大最大流的邊只會是連接S和T所在聯(lián)通分量的邊。

總結(jié)

以上是生活随笔為你收集整理的P4126 [AHOI2009]最小割(网络流/最小割）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。