Server Time：

74 . 次小生成樹

Submit
Status
Ranklist
Back to Problems List

User's AC Ratio in this contest

30.0% (3/10)

Submission's AC Ratio in this contest

14.3% (3/21)

Tags

2020 高階競技程式設計 - Contest #7

Description

給定一張圖，請輸出這張圖的次小生成樹上，所有邊的權重和

Input Format

第一行有兩個整數 $N, M$ ，代表圖中點的數量與邊的數量
接下來 $M$ 行，每行有三個數字 $u_i, v_i, w_i$ ，代表有一條邊連接 $u_i$ 與 $v_i$ 且其權重為 $w_i$

  • $N \le 2 \times 10 ^ 5$
  • $M \le 5 \times 10 ^ 5$
  • $0 \le u_i, v_i \lt N, 0 \lt w_i \le 10 ^ 3$

Output Format

請輸出這張圖的次小生成樹上，所有邊權重的和
如果有複數的最小生成樹，即認為其中一個便是次小生成樹

Sample Input 1

5 10
1 2 4
0 4 4
0 2 8
4 1 1
0 3 6
0 1 3
1 2 7
0 2 10
0 1 6
3 4 10

Sample Output 1

15

Hints

沒有為什麼，就只是想要放一張老婆的圖

都最後一場了就讓我放一下嘛 QAQ

Problem Source

Subtasks

No. Testdata Range Score
1 0~19 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 131072 65536 1
1 2000 131072 65536 1
2 2000 131072 65536 1
3 2000 131072 65536 1
4 2000 131072 65536 1
5 2000 131072 65536 1
6 2000 131072 65536 1
7 2000 131072 65536 1
8 2000 131072 65536 1
9 2000 131072 65536 1
10 2000 131072 65536 1
11 2000 131072 65536 1
12 2000 131072 65536 1
13 2000 131072 65536 1
14 2000 131072 65536 1
15 2000 131072 65536 1
16 2000 131072 65536 1
17 2000 131072 65536 1
18 2000 131072 65536 1
19 2000 131072 65536 1
Submit
Status
Ranklist
Back to Top