BOJ 6497: 전력난

최소한으로 가로등을 켜야 하는 문제이므로 최소 스패닝 트리를 이용하여 문제를 풀 수 있다. 프림 알고리즘을 사용하여 켜야 하는 가로등의 총 비용을 구한 뒤 총 비용에서 켠 가로등의 총 비용을 빼면 절약할 수 있는 비용을 구할 수 있다.