문제 링크 https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 문제 풀이 그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다. 위의 지문이 조금 이해가 안되었는데, 사이클이 발생하는 경우에 대해 설명하는 것으로 이해했다. - 크루스칼/프림 알고리즘 (최소 신장트리,MST) 사용하여 최소 비용을 구한 후 전체 비용과의 차..