網絡流最小割相關（持續更新）

（12.6）

今天看了下網絡流，本想寫一篇部落格，但是想了想，畫圖太費勁，證明也不算特别難，那就先咕着了。

前置知識：網絡最大流（最好是dinic算法），最大流最小割定理。

一、割邊最少的最小割

題目：

hdu3987 http://acm.hdu.edu.cn/showproblem.php?pid=3987

hdu6214 http://acm.hdu.edu.cn/showproblem.php?pid=6214 (雙倍經驗)

方法一：（一次dinic）

我們首先考慮，如何在求最大流的同時兼顧最小割的邊數。

第一感覺是類似費用流，給每一條邊加一維費用，但仔細思考後發現不用。我們完全可以直接對于每一條邊的容量+1，那麼最後所求出的最大流一定會保證最小割的邊數最少。證明：

設原圖最小割為S，那麼我們對于每一條邊容量+1後，目前圖最小割變為S + P(P為最小割的邊數)，顯然可以得到，當P最小時，取得目前圖的最小割，即保證了最小割的最少割邊。

但是，這樣做會改變原圖的最小割。當然，我們可以做兩次dinic，但是這需要你常數夠好不怕卡常。如果我們隻做一次dinic，顯然我們需要做到的是：去掉邊數對答案的影響。這裡有一個操作：

将原圖中每一條邊的容量*(maxp + 1)（maxp為圖中最大邊數）+ 1。

那麼目前圖的最小割為S * (maxp + 1) + P(P為最小割的邊數)。

顯然P < maxp + 1，那麼我們對目前的最小割除以(maxp + 1)就是原圖的最小割，取模(maxp + 1)就是原圖最小割的最少割邊。

代碼不想寫了。

方法二：（兩次dinic）

我們在第一次dinic求出來最大流時，由于最小割中的邊都是滿流邊，那麼問題轉化為，最少删掉幾條滿流邊可以使圖不連通。

仔細想想，目前那個問題不也是求一個最小割嗎？那麼我們不妨重新構圖（其實隻是修改了容量），對于滿流邊将它的容量改為1，其它邊的容量改為無窮大。這樣，求出來的最小割即為最少割邊啦。

代碼也不寫啦，都是闆子。

二、最小割樹

咕咕咕！