給出一個 N 點 M 邊的連通無向圖,任兩條邊的邊權皆不相同。
首先我們先從圖 G 上挑選出一個生成樹 T。
接著對於一個點 u 來說,我們稱點 u 是「好點」若且唯若 u 想要以最短路徑抵達圖 G 上任一點都可以只透過這棵生成樹達到。
請找到一個滿足邊權總和最小的生成樹 T′,倘若有多個可能請選擇有最多「好點」的那棵生成樹,如果仍有很多棵樹,則可以任選一棵,並找出這個樹上有哪些好點。
測試資料第一行包含兩個正整數 N,M ,代表圖 G 上的點數與邊數。
接下來一共有 M 行,每行會有三個正整數 ui,vi,wi 代表圖上有一條 ui 到 vi 邊權為 wi 的邊。
第一行請輸出一個數字 n 代表你選擇的生成樹 T′ 上有幾個「好點」。
第二行請由小到大輸出一共 n 個數字,代表生成樹 T′ 上每個好點的編號。
IOICamp 2021 Day5 pH