最小生成樹

1/5ページ

【SOJ 973】Tree

emmm…… 今天第二題正解程式碼有點複雜,我先寫第三題   【題目】 題目描述: 給你一個有 N 個點 M 條邊的無向帶權連通圖,每條邊是白色或黑色,求一顆最小權的恰好有 K 條白邊的生成樹。 輸入格式: 第一行三個數 N、M、K ,分別表示點數、邊數和所需的白邊數。 接下來 M 行,每行四個數  […]

【SOJ 1824】保留道路

【題目】 題目描述: 很久很久以前有一個國家,這個國家有 N 個城市,城市由 1,2,3,…,N 標號,城市間有 M 條雙向道路,每條道路都有兩個屬性 g 和 s ,兩個城市間可能有多條道路,並且可能存在將某一城市與其自身連線起來的道路。後來由於戰爭的原因,國王不得不下令減小花費從而關閉一些道路,但 […]

圖-最小生成數-prims演算法

演算法步驟 1:從一個點比如為Q出發,找出它能到達其他頂點的所有邊的最小值邊,記錄該點比如為W。 2:從上次記錄的點W出發,重新執行1的操作,這時候的邊要與上次對應的邊值進行比較。 比如Q到P為4,而W到P為6,那麼記錄W到P仍然為4。 3:重複直至所有點被記錄 ——R […]