772 . 最小生成樹

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

75.0% (3/4)

Tags

apcsc apcsc-graph

Description

上課中，我們有學到「Minimum Spanning Tree最小生成樹」，現在小熊手上有一些無向圖（不一定會連通喔 ><），興高采烈地求出了最小生成森林拿給老師看，老師卻說小熊沒有考慮到重邊與自環的問題，小熊十分懊惱！聰明的你可以幫助小熊，在圖有可能有重邊與自環的情況下，求出最小生成森林的邊權和嗎？

Input Format

第一行會輸入兩個正整數 $N$, $M$ 代表點數跟邊數
接下來 $M$ 行每行有三個正整數 $a, b, c$，代表 $a, b$ 之間有一條權重為 $c$ 的邊

  • $1 \le N \le 2 \cdot 10^ 5$
  • $1 \le M \le 4 \cdot 10^ 5$
  • $1 \le a, b \le N$
  • $1 \le c \le 10^ 9$

Output Format

輸出只有一行，代表這個最小生成森林邊權的和。

Sample Input 1

5 7
1 2 5
1 3 8
1 4 9
2 3 4
2 5 15
3 5 6
4 5 3

Sample Output 1

18

Hints

Problem Source

Subtasks

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

Testdata and Limits

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