최소 신장 트리
골드 IV의견: 0
가중치가 있는 무방향 연결 그래프가 주어진다. 이 그래프의 최소 신장 트리(Minimum Spanning Tree)의 가중치를 구하는 프로그램을 작성하시오.
최소 신장 트리란, 그래프의 모든 정점을 연결하는 부분 그래프(트리) 중에서 사용된 간선들의 가중치의 합이 가장 작은 것을 말한다. 그래프는 항상 연결되어 있으므로 최소 신장 트리는 반드시 존재한다.
- \(1 \le V \le 10\,000\)
- \(1 \le E \le 100\,000\)
- \(1 \le A, B \le V\)
- \(-10^6 \le C \le 10^6\)
- 그래프는 연결되어 있다.
- 입력으로 주어지는 모든 값은 정수이다.
첫째 줄에 정점의 개수 \(V\)와 간선의 개수 \(E\)가 주어진다. 정점은 \(1\)번부터 \(V\)번까지 번호가 매겨져 있다.
다음 \(E\)개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 \(A\), \(B\), \(C\)가 주어진다. 이는 \(A\)번 정점과 \(B\)번 정점이 가중치 \(C\)인 간선으로 연결되어 있다는 의미이다. \(C\)는 음수일 수도 있다.
같은 두 정점 사이에 여러 개의 간선이 있을 수 있으며, 양 끝 정점이 같은 간선(\(A = B\))이 주어질 수도 있다.
최소 신장 트리의 가중치의 합을 한 줄에 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 30점 | \(1 \le V \le 100,\ 1 \le E \le 2\,000\) |
Subtask 2 | 30점 | 모든 간선의 가중치가 \(0\) 이상이다 (\(0 \le C\)). |
Subtask 3 | 40점 | 추가 제한이 없다. |
3 3
1 2 1
2 3 2
1 3 33간선 \(1\!-\!2\) (가중치 \(1\))와 \(2\!-\!3\) (가중치 \(2\))를 고르면 세 정점이 모두 연결되고, 가중치의 합은 \(1 + 2 = 3\)으로 최소이다.
4 5
1 2 1
2 3 3
1 3 2
3 4 -4
2 4 5-1간선 \(3\!-\!4\) (가중치 \(-4\)), \(1\!-\!2\) (가중치 \(1\)), \(1\!-\!3\) (가중치 \(2\))를 고르면 모든 정점이 연결되며 합은 \(-4 + 1 + 2 = -1\)이다. 음수 가중치 간선도 사용될 수 있다.
5 6
1 2 5
2 3 8
1 3 4
3 4 2
4 5 7
2 5 617간선 \(3\!-\!4\) (\(2\)), \(1\!-\!3\) (\(4\)), \(1\!-\!2\) (\(5\)), \(2\!-\!5\) (\(6\))를 고르면 가중치의 합은 \(2 + 4 + 5 + 6 = 17\)로 최소이다.
rip 작성
출처 지정되지 않음
평가 및 의견
최소 신장 트리
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
최소 신장 트리