TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

37.5% (3/8)

Tags

Description

給出一個 NM 邊的連通無向圖,任兩條邊的邊權皆不相同。

首先我們先從圖 G 上挑選出一個生成樹 T

接著對於一個點 u 來說,我們稱點 u 是「好點」若且唯若 u 想要以最短路徑抵達圖 G 上任一點都可以只透過這棵生成樹達到。

請找到一個滿足邊權總和最小的生成樹 T,倘若有多個可能請選擇有最多「好點」的那棵生成樹,如果仍有很多棵樹,則可以任選一棵,並找出這個樹上有哪些好點。

Input Format

測試資料第一行包含兩個正整數 N,M ,代表圖 G 上的點數與邊數。

接下來一共有 M 行,每行會有三個正整數 ui,vi,wi 代表圖上有一條 uivi 邊權為 wi 的邊。

  • 1N3×105
  • 1M3×105
  • 1ui,viN
  • 1wi1012

Output Format

第一行請輸出一個數字 n 代表你選擇的生成樹 T 上有幾個「好點」。

第二行請由小到大輸出一共 n 個數字,代表生成樹 T 上每個好點的編號。

Sample Input 1

8 8
1 2 100
2 3 20
2 8 19
8 6 18
6 7 23
3 4 10
4 5 2
4 7 21

Sample Output 1

2
1 2

Hints

Problem Source

IOICamp 2021 Day5 pH

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~33 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 262144 65536 1 2
1 2000 262144 65536 2
2 2000 262144 65536 2
3 2000 262144 65536 2
4 2000 262144 65536 2
5 2000 262144 65536 2
6 2000 262144 65536 2
7 2000 262144 65536 2
8 2000 262144 65536 2
9 2000 262144 65536 2
10 2000 262144 65536 2
11 2000 262144 65536 2
12 2000 262144 65536 2
13 2000 262144 65536 2
14 2000 262144 65536 2
15 2000 262144 65536 2
16 2000 262144 65536 2
17 2000 262144 65536 2
18 2000 262144 65536 2
19 2000 262144 65536 2
20 2000 262144 65536 2
21 2000 262144 65536 2
22 2000 262144 65536 2
23 2000 262144 65536 2
24 2000 262144 65536 2
25 2000 262144 65536 2
26 2000 262144 65536 2
27 2000 262144 65536 2
28 2000 262144 65536 2
29 2000 262144 65536 2
30 2000 262144 65536 2
31 2000 262144 65536 2
32 2000 262144 65536 2
33 2000 262144 65536 2