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