R00753
최소 스패닝 트리
골드 IV레이팅
의견: 0
설명
연결된 무방향 가중치 그래프가 주어진다. 모든 정점을 연결하는 부분 그래프 중 간선 가중치의 합이 최소인 것(최소 스패닝 트리)의 가중치 합을 구하여라.
두 정점 사이에 간선이 여러 개 있을 수 있으며, 가중치는 음수일 수도 있다.
제약
\(2 \le V \le 10\,000\), \(1 \le E \le 100\,000\), \(|C| \le 10\,000\). 그래프는 항상 연결되어 있다.
입력 형식
첫째 줄에 정점의 개수 \(V\)와 간선의 개수 \(E\)가 주어진다. 다음 \(E\)개의 줄에 간선의 양 끝 정점과 가중치 \(A\ B\ C\)가 주어진다.
출력 형식
최소 스패닝 트리의 가중치 합을 출력한다.
예제 1
입력
3 3
1 2 1
2 3 2
1 3 3
출력
3
설명
간선 \((1,2)\)와 \((2,3)\)을 고르면 가중치 합 \(3\)으로 최소이다.
예제 2
입력
4 5
1 2 -4
2 3 -1
3 4 -6
1 4 2
1 3 5
출력
-11
설명
가중치가 음수일 수도 있다. 합은 \(-11\).
다이아몬드 I문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
최소 스패닝 트리
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
최소 스패닝 트리
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기