7206 : 최소 스패닝 완전탐색
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N개의 정점과 M개의 간선으로 이루어진 가중치 그래프가 주어집니다. 완전탐색을 통해 그래프의 모든 정점을 연결하면서 사이클이 없는 최소 스패닝 트리(MST)의 가중치 합을 구하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어집니다. (1 ≤ N ≤ 10, M은 간선 수)
둘째 줄부터 M개의 줄에 간선의 정보(u, v, w)가 주어집니다.
둘째 줄부터 M개의 줄에 간선의 정보(u, v, w)가 주어집니다.
출력 설명
최소 스패닝 트리의 가중치 합을 출력합니다. 연결이 불가능하면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 5
1 2 10
1 3 6
1 4 5
2 4 15
3 4 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
19도움
크루스칼 알고리즘 기준 간선을 가중치 오름차순으로 정렬하면 (3,4,4), (1,4,5), (1,3,6), (1,2,10), (2,4,15)입니다. 사이클 없이 모든 정점을 연결하는 최소 스패닝 트리는 간선 (3,4,4), (1,4,5), (1,2,10)을 선택하여 가중치 합 4+5+10=19가 됩니다.