主要談?wù)劷▓D的原理給自己聽

首先貪心出來的一個圖上加的邊都是可走的【修改邊】，這些修改邊的反向邊是用來在跑網(wǎng)絡(luò)流的時候撤銷修改的

換句話說，每條修改邊都是備選項，是用來調(diào)整圖上各點(diǎn)入度的

所以，既然是保存修改邊，那么圖里是不保存我們原本貪心保留的邊的，那些邊的信息都被壓縮進(jìn)最低消耗和各點(diǎn)的入度了

把貪心邊引發(fā)的信息稱為初始流，我現(xiàn)在需要一個附加流，附加流疊加上初始流能讓各點(diǎn)的入度變?yōu)?

假設(shè)初始流中u點(diǎn)的入度為正x，意即u點(diǎn)的入度大于出度

那么附加流中就需要讓u的出度大于入度

為了跑出這樣一個并不平衡的流，我要從虛擬源節(jié)點(diǎn)s向u連一條容量為u入度絕對值的邊

這樣在跑最大流的時候，u會往更多的點(diǎn)進(jìn)行增廣，這樣也就達(dá)到了修正入度為0的目的

這里的增廣即是走修改邊

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

總結(jié)

以上是生活随笔為你收集整理的Random Maze HDU - 4067 费用流/可行流的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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