BOJ 6497 전력난

 

BOJ 백준 6497 C++

전력난

https://www.acmicpc.net/problem/6497

 

1) MST(최소 신장 트리)의 Kruskal(union find 이용) 문제

2) 벡터에 주어진 (from, to, dist)를 삽입 후 dist의 오름차순으로 정렬한 후, 차례대로 꺼내며 하나의 집합으로 만든다.

3) 집보다 길의 수가 (훨씬) 많이 주어질 수 있다. 연결된 길(cnt)이 [집의 수-1]개가 되었을 때 종료한다.

-> 이 때 종료되면, 하나의 집합을 이룰 때 최소 비용을 구할 수 있다.

4) 문제에서는 절약할 수 있는 비용을 원하므로, 전체 비용에서 최소 비용을 빼면 답을 구할 수 있다.

5) testcase도 여러 개 주어질 수 있다. 정보를 저장한 벡터를 비우거나, 새 테스트케이스마다 새로 만들어야 한다.