USACO 4_1_3 Fence Loops
摘要: 題意就是求最小周長(zhǎng),一開始我想畫成圖論,然后用類似dij的算法求最小環(huán)長(zhǎng),可是發(fā)現(xiàn)兩個(gè)端點(diǎn)會(huì)出現(xiàn)沖突.我一開始的思路是,把每塊木板當(dāng)成一個(gè)點(diǎn),然后選一個(gè)端點(diǎn)當(dāng)成出邊,另外一個(gè)端點(diǎn)當(dāng)成入邊,權(quán)值等于"起點(diǎn)"[這里是某快木板]的長(zhǎng)度,可是會(huì)出現(xiàn)沖突,樣例就是一個(gè)很好的例子,會(huì)出現(xiàn)到了某個(gè)點(diǎn)是,它必須又是起始點(diǎn)又是終止點(diǎn).那么這樣就出問題了.
閱讀全文