【最小割】bzoj:1797最小割

一個有向圖，源點s，彙點t，問哪些邊能夠出現在某個最小割集中，哪些邊必定出現在最小割集中。

求最大流，在殘餘網絡上跑tarjan求出所有SCC，記id[u]為點u所在SCC的編号。顯然有id[s]!=id[t]（否則s到t有通路，能繼續增廣）。

①對于任意一條滿流邊(u,v)，(u,v)能夠出現在某個最小割集中，當且僅當id[u]!=id[v]；

②對于任意一條滿流邊(u,v)，(u,v)必定出現在最小割集中，當且僅當id[u]==id[s]且id[v]==id[t]。

簡要寫一下證明：

首先，由最大流最小割定理易知最小割中的割邊一定是滿流邊。

①

==>如果id[u]==id[v]，則殘餘網絡存在u->v的通路，通過(u,v)的割也必然通過這條通路上的某條非滿流邊，不會是最小割。

<==将每個SCC縮成一個點，得到的新圖就隻含有滿流邊了。那麼新圖的任一s-t割都對應原圖的某個最小割，從中任取一個把id[u]和id[v]割開的割即可證明。

②

<==：假設将(u,v)的邊權增大，那麼殘餘網絡中會出現s->u->v->t的通路，進而能繼續增廣，于是最大流流量（也就是最小割容量）會增大。這即說明(u,v)是最小割集中必須出現的邊。

==>：上面的證明可以反推回去，略。

每次都推容易錯，還是記住結論好些。