拆點(diǎn)是一種圖論建模思想，常用于網(wǎng)絡(luò)流，用來處理點(diǎn)權(quán)或者點(diǎn)的流量限制的問題，也常用于分層圖。

一、什么是拆點(diǎn)？

什么是拆點(diǎn)？拆點(diǎn)就是將一個(gè)點(diǎn)拆成入點(diǎn)和出點(diǎn)兩個(gè)點(diǎn)，并在兩個(gè)點(diǎn)之間建一條邊。

為什么要拆點(diǎn)？拆點(diǎn)是為了實(shí)現(xiàn)對(duì)點(diǎn)的限制。

什么時(shí)候需要拆點(diǎn)？當(dāng)題目中明確說明對(duì)點(diǎn)有限制或在實(shí)際應(yīng)用中對(duì)點(diǎn)有限制時(shí)，我們就需要拆點(diǎn)。例如我們要保證經(jīng)過某點(diǎn)中轉(zhuǎn)的流量不能大于5（對(duì)點(diǎn)有流量限制），那么我們就需要將該點(diǎn)拆成入點(diǎn)和出點(diǎn)，并在兩點(diǎn)間建一條容量為5的邊，就實(shí)現(xiàn)了對(duì)點(diǎn)的限制。

做題時(shí)一定要看清，如果是對(duì)邊有限制，就通過流量或流網(wǎng)絡(luò)來實(shí)現(xiàn)；如果是對(duì)點(diǎn)有限制，就通過拆點(diǎn)來實(shí)現(xiàn)。

二、結(jié)點(diǎn)有流量限制的最大流

如果把結(jié)點(diǎn)轉(zhuǎn)化成邊，那么這個(gè)問題就可以套板子解決了。

我們考慮把有流量限制的結(jié)點(diǎn)轉(zhuǎn)化成這樣一種形式：由兩個(gè)結(jié)點(diǎn) u,v 和一條邊 <u,v> 組成的部分。其中，結(jié)點(diǎn) u 承接所有從原圖上其他點(diǎn)的出發(fā)到原圖上該點(diǎn)的邊，結(jié)點(diǎn) v 引出所有從原圖上該點(diǎn)出發(fā)到達(dá)原圖上其他點(diǎn)的邊。邊 <u,v> 的流量限制為原圖該點(diǎn)的流量限制，再套板子就可以解決本題。這就是拆點(diǎn)的基本思想。

如果原圖是這樣：

拆點(diǎn)之后的圖是這個(gè)樣子：

三、分層圖最短路

分層圖最短路，如：有 k 次零代價(jià)通過一條路徑，求總的最小花費(fèi)。對(duì)于這種題目，我們可以采用 DP 相關(guān)的思想，設(shè)  表示當(dāng)前從起點(diǎn) i 號(hào)結(jié)點(diǎn)，使用了 j 次免費(fèi)通行權(quán)限后的最短路徑。顯然，dis數(shù)組可以這么轉(zhuǎn)移：

其中，from表示 i 的父親節(jié)點(diǎn)，w 表示當(dāng)前所走的邊的邊權(quán)。當(dāng) j-1≥k 時(shí)，。

事實(shí)上，這個(gè) DP 就相當(dāng)于把每個(gè)結(jié)點(diǎn)拆分成了 k+1 個(gè)結(jié)點(diǎn)，每個(gè)新結(jié)點(diǎn)代表使用不同多次免費(fèi)通行后到達(dá)的原圖結(jié)點(diǎn)。換句話說，就是每個(gè)結(jié)點(diǎn) ui 表示使用 i 次免費(fèi)通行權(quán)限后到達(dá) u 結(jié)點(diǎn)。