題解:P14080 [GESP202509 八級(jí)] 最小生成樹(shù)
題目:
跑原圖最小生成樹(shù),刪的邊不在樹(shù)上答案就是這個(gè),在樹(shù)上考慮如何連接 \(u\) 的連通塊和 \(v\) 的連通塊,從非樹(shù)邊中選,腦子空想是類似路徑差分 \(\min\),但手畫(huà)一下其實(shí)就是路徑 \(\min\)。自己畫(huà)!
非樹(shù)邊 \((a,b,c)\),在最小生成樹(shù)上 \(a→b\) 的邊區(qū)間 \(\min\) 一下 \(c\)(邊權(quán)下發(fā)),查詢樹(shù)邊輸出當(dāng)前邊 \(\min\)。

浙公網(wǎng)安備 33010602011771號(hào)