문제 1151 최소 신장 트리 (AI)
[만든사람 : ]
문제 설명
무방향 가중치 그래프가 주어질 때, 그 그래프의 최소 신장 트리를 구하세요.
최소 신장 트리는 모든 정점을 포함하고 가중치의 합이 최소가 되는 트리입니다.
예를 들어, 다음과 같은 그래프가 주어질 때:
1 -- 2 -- 3
| / | /
4 -- 5
각 간선의 가중치가 다음과 같다고 합시다:
1-2: 2, 2-3: 3, 1-4: 6, 4-5: 8, 5-2: 5, 2-4: 2
최소 신장 트리는 다음과 같으며, 가중치의 합은 17입니다:
1 -- 2 -- 3
| /
4 -- 5
입력 설명
첫 줄에 정점의 수 V와 간선의 수 E가 주어집니다. 그 다음 E개의 줄에 간선의 정보가 주어집니다. 각 줄은 세 정수 u, v, w로 구성되며, 이는 정점 u와 v가 가중치 w인 간선으로 연결되어 있음을 의미합니다.
출력 설명