8042 : 도로 보수
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 도시와 이들 사이에 도로를 보수하기 위해 필요한 견적 비용이 명시된 $M$개의 정보가 양방향 도로 가중치 그래프로 주어집니다.
모든 도시가 서로 오갈 수 있도록 연결하면서 도로의 총 보수 비용을 최소화하려고 합니다. 필요한 최소 보수 비용의 총합을 구하는 프로그램을 작성하시오.
[제약 조건]
• $1 \le N \le 100{,}000$
• $1 \le M \le 200{,}000$
• $1 \le a, b \le N$
• $1 \le c \le 10^9$
모든 도시가 서로 오갈 수 있도록 연결하면서 도로의 총 보수 비용을 최소화하려고 합니다. 필요한 최소 보수 비용의 총합을 구하는 프로그램을 작성하시오.
[제약 조건]
• $1 \le N \le 100{,}000$
• $1 \le M \le 200{,}000$
• $1 \le a, b \le N$
• $1 \le c \le 10^9$
입력 설명
첫째 줄에 도시의 수 $N$과 도로의 수 $M$이 공백으로 구분되어 주어집니다. ($1 \le N \le 100,000$, $1 \le M \le 200,000$)
다음 $M$개의 줄에 걸쳐 도로가 잇는 두 도시 $a, b$와 보수 견적 비용 $c$가 주어집니다. ($1 \le a, b \le N$, $1 \le c \le 10^9$)
다음 $M$개의 줄에 걸쳐 도로가 잇는 두 도시 $a, b$와 보수 견적 비용 $c$가 주어집니다. ($1 \le a, b \le N$, $1 \le c \le 10^9$)
출력 설명
최소 도로 보수 비용의 총합을 출력합니다. 만약 모든 도시를 도로망으로 연결하는 것이 불가능하다면
IMPOSSIBLE을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 6
1 2 3
2 3 5
2 4 2
3 4 8
5 1 7
5 4 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
14도움
이 문제는 주어진 가중치 그래프에서 최소 신장 트리(Minimum Spanning Tree, MST)를 구하는 문제입니다.
크루스칼(Kruskal) 알고리즘 또는 프림(Prim) 알고리즘을 활용합니다.
크루스칼 알고리즘 적용 시 모든 간선을 비용 기준으로 오름차순 정렬한 뒤, Union-Find 자료구조를 통해 두 정점이 사이클을 이루지 않을 때만 간선을 선택해 연결해 나갑니다. 최종 선택한 간선 수가 $N-1$개가 아니라면 연결이 불가능한 상태이므로
크루스칼(Kruskal) 알고리즘 또는 프림(Prim) 알고리즘을 활용합니다.
크루스칼 알고리즘 적용 시 모든 간선을 비용 기준으로 오름차순 정렬한 뒤, Union-Find 자료구조를 통해 두 정점이 사이클을 이루지 않을 때만 간선을 선택해 연결해 나갑니다. 최종 선택한 간선 수가 $N-1$개가 아니라면 연결이 불가능한 상태이므로
IMPOSSIBLE을 처리합니다.