類似于Kruskal算法，所有邊從小到大排序，枚舉每一條邊建公路，直到所有的點(diǎn)都能連通為止（用并查集判斷）
然后我去網(wǎng)上查了一下別人的代碼，我查到的所有人都說是求最小生成樹的最長邊的權(quán)值，但是如果真的是這樣，那這一組數(shù)據(jù)他絕對(duì)是過不了的。140 2 3 21 0 2 33 2 0 22 3 2 0但是，我把他們的代碼復(fù)制下來，然后用這組數(shù)據(jù)試了一下，發(fā)現(xiàn)居然都能得出正確答案，也不知道他們代碼都是怎么寫的。現(xiàn)在舉例說明：最小生成樹的最長邊權(quán)值并不等價(jià)于使圖連通的所有邊的最長邊的可能取到的最小值。
如本圖所示，即上組測試數(shù)據(jù)的圖，顯然，最小生成樹的所有邊的和應(yīng)該是7，此時(shí)最長邊應(yīng)該是3，但是，但是，但是，四條權(quán)值為2的邊就可以使圖連通，最長邊的可能取到的最小值為2！備注：代碼完全手打，一次ac，并查集魔板（魔法的魔）回來一定要好好整理一個(gè)。
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
