?

最大權(quán)閉合子圖（最大流最小割）

?參考資料

【1】最大權(quán)閉合子圖

?權(quán)閉合子圖

存在一個圖的子圖，使得子圖中的所有點出度指向的點依舊在這個子圖內(nèi)，則此子圖是閉合子圖。

?在這個圖中有8個閉合子圖：?,{3},{4},{2,4},{3,4},{1,3,4},{2,3,4},{1,2,3,4}

?最大權(quán)閉合子圖

在一個圖中每個點具有點權(quán)值，在他的所有閉合子途中點權(quán)之和最大的即是最大權(quán)閉合子圖。

?詳解

• 最大權(quán)閉合子圖
• 結(jié)論

最大權(quán)閉合子圖權(quán)值 ?= ?所有權(quán)值為正的權(quán)值之和 ?- ?最大流

?步驟

• 建圖

抽象出一個超級源、匯點

將權(quán)值為正的點和超級源點連接、容量為權(quán)值

將權(quán)值為負(fù)的點和超級匯點連接、容量為權(quán)值的絕對值

除了源、匯之外的點原本按題目關(guān)系相連，容量為無窮大

• 計算

最大權(quán)閉合子圖權(quán)值 ?= ?所有權(quán)值為正的權(quán)值之和 ?- ?最大流

?例題

【題目】

BZOJ 1497 最大獲利

HOJ 2634? How to earn more

【代碼】

HOJ?2634 How to earn more

?

轉(zhuǎn)載于:https://www.cnblogs.com/MMMinoz/p/11620078.html

總結(jié)

以上是生活随笔為你收集整理的最大权闭合子图(最小割)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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