P2764 最小路徑覆蓋問(wèn)題

最小鏈覆蓋問(wèn)題，關(guān)鍵在于怎么轉(zhuǎn)化為網(wǎng)絡(luò)流問(wèn)題，我們可以發(fā)現(xiàn)網(wǎng)絡(luò)流的常見(jiàn)套路就是將一個(gè)點(diǎn)拆成出點(diǎn)和入點(diǎn)來(lái)處理，對(duì)于一條鏈恰好滿足出點(diǎn)和入點(diǎn)匹配的性質(zhì)，所以可以拆點(diǎn)然后對(duì)應(yīng)連邊，這樣跑最大流得到的就是鏈的最大長(zhǎng)度，容易求出鏈的個(gè)數(shù)。

拆成入點(diǎn)和出點(diǎn)匹配
**最小邊覆蓋=點(diǎn)總數(shù)-最大匹配 **

總結(jié)

以上是生活随笔為你收集整理的P2764 最小路径覆盖问题（网络流）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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