求圖的頂點(diǎn)連通度算法。方法就是先對(duì)源和匯做枚舉，之后對(duì)每個(gè)枚舉情況，把除去源匯兩點(diǎn)的其余所有頂點(diǎn)看成是容量限制為1的點(diǎn)，求網(wǎng)絡(luò)的最大流，就是此點(diǎn)對(duì)的頂點(diǎn)連通度，之后對(duì)枚舉的所有點(diǎn)對(duì)找連通度最小的當(dāng)成圖的連通度。
帶有頂點(diǎn)容量限制的最大流方法：將帶容量限制的頂點(diǎn)u拆成兩個(gè)點(diǎn)u 和u*，原頂點(diǎn)u的入邊為u 的入邊，原頂點(diǎn)u的出邊為u*的出邊，之后在u 和u*之間連接雙向邊，邊的容量為頂點(diǎn)的容量限制。
標(biāo)簽：
算法
上傳時(shí)間：
2013-12-21
上傳用戶：515414293
