1099: [브론즈-78]원더랜드(Kruskal MST 알고리즘 : Union&Find 활용)
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다.
원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지
도로는 폐쇄하려고 한다.
아래의 그림은 그 한 예를 설명하는 그림이다.
원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지
도로는 폐쇄하려고 한다.
아래의 그림은 그 한 예를 설명하는 그림이다.
위의 지도는 각 도시가 1부터 9로 표현되었고, 지도의 오른쪽은 최소비용 196으로 모든 도시
를 연결하는 방법을 찾아낸 것이다.
Input
첫째 줄에 도시의 개수 V(1≤V≤25)와 도로의 개수 E(1≤E≤200가 주어진다. 다음 E개의 줄에
는 각 도로에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 도시와 B번 도시
가 유지비용이 C인 도로로 연결되어 있다는 의미이다. C는 값이 1,000,000을 넘지 않는다.
는 각 도로에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 도시와 B번 도시
가 유지비용이 C인 도로로 연결되어 있다는 의미이다. C는 값이 1,000,000을 넘지 않는다.
Output
모든 도시를 연결하면서 드는 최소비용을 출력한다.
Sample Input Copy
9 12
1 2 12
1 9 25
2 3 10
2 8 17
2 9 8
3 4 18
3 7 55
4 5 44
5 6 60
5 7 38
7 8 35
8 9 15Sample Output Copy
196HINT
출처 : Mid-Central USA 2002