網絡流刷題記錄-最小割

個人覺得最小割比最大流無聊多了==

HOJ 2713 Matrix1

BZOJ 1497 [NOI2006]最大獲利

HDU 1565 方格取數(1)

POJ 1815 Friendship

ZOJ 2532(由于ZOJ依舊挂着是以是vjduge)

HOJ 2713 Maxtirx1&HDU 1565 方格取數(1)

HOJ那題和HDU完全相同==

都是一個叫“最大點權獨立集”的東西。

關于這東西怎麼搞，幹脆直接記公式：

最大點權獨立集=總權和-最小點權覆寫集 最小點權覆寫集=最小割=最大流

證明懶得看了，反正哥記性好-0-

BZOJ 1497 [NOI2006]最大獲利

這題是那個最大權閉和圖， ans=∑v∈V+w[v]−c[S,T]

裸的

POJ 1815 Friendship

這題算是有點意思的。

先拆點，除了s和t，其他拆成兩個點，中間連一條 c=1 的邊。

然後按照給出的圖，連 c=INF 的邊。

我們跑出最小割。這是顯然的。

然後既然要求按字典序輸出答案，不如我們直接從1到n枚舉丢掉哪個點。

沒丢掉一個跑一下最小割，看看最小割有沒有變化，若變小那麼說明這個點得丢，否則就塞回去。

ZOJ 2532 Internship

這題是最小割？

不過這題還是很神的。

首先跑一下最大流。

然後check一下邊，如果變成了0，那麼就是要找到了。