5266 : A67 - 최소 신장 트리
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
정점 수 $N$ , 간선 수 $M$ 의 그래프가 주어집니다. 정점에는 1부터 $N$ 까지 번호가 붙어 있으며, 간선 $i$ 는 정점 $A_i$ 와 $B_i$ 를 양방향으로 연결하는 길이 $C_i$ 의 간선입니다. 이 그래프의 최소 신장 트리에서 간선 길이의 총합을 구하세요.
[제약 조건]
• $2 \le N \le 100000$
• $1 \le M \le 100000$
• $1 \le A_i \lt B_i \le N$
• $i \neq j$ 이면 $(A_i,B_i) \neq (A_j,B_j)$ 입니다.
• $1 \le C_i \le 10000$
• 주어지는그래프는 연결되어 있습니다.
• 입력되는 모든 값은 정수입니다.
[제약 조건]
• $2 \le N \le 100000$
• $1 \le M \le 100000$
• $1 \le A_i \lt B_i \le N$
• $i \neq j$ 이면 $(A_i,B_i) \neq (A_j,B_j)$ 입니다.
• $1 \le C_i \le 10000$
• 주어지는그래프는 연결되어 있습니다.
• 입력되는 모든 값은 정수입니다.
입력 설명
첫째 줄에 $N, M$ 이 주어집니다.
둘째 줄부터 $M$ 개의 줄에 걸쳐 간선 정보 $A_i, B_i, C_i$ 가 주어집니다.
둘째 줄부터 $M$ 개의 줄에 걸쳐 간선 정보 $A_i, B_i, C_i$ 가 주어집니다.
출력 설명
최소 신장 트리의 간선 가중치 합을 출력하세요.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
7 9
1 2 12
1 3 10
2 6 160
2 7 15
3 4 1
3 5 4
4 5 3
4 6 120
6 7 14
출력 예시
COPY
복사되었습니다!
복사되었습니다!
55