5366 : B67 - 최대 스패닝 트리
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
정점 수 $N$, 간선 수 $M$인 그래프의 최대 스패닝 트리(Maximum Spanning Tree)의 모든 간선 가중치 합을 구하십시오.
[제약 조건]
• $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
복사되었습니다!
복사되었습니다!
321