[백준][C++] 6497 전력난

6497. 전력난 문제 풀이 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다.

그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 기본적인 MST 문제였다.

전체 비용 - MST의 비용이 절약할 수 있는 최대 비용이기 때문이다. 알고리즘 설계 간선을 입력받으며 간선들과 간선들의 모든 가중치를 더해 저장한다.

간선들을 가중치 기준으로 오름차순 정렬한다. union-find와 memoization을 사용해 사이클이 생기지 않게 크루스칼 알고리즘을 이용해 MST의 비용을 구한다. 모든 간선의 가중치의 합 - MST 비용을 출력한다.

코드 #include using namespa.....