반갑습니다!

[백준] 6497 전력난 본문

알고리즘 문제 풀이

[백준] 6497 전력난

김덜덜이 2020. 10. 19. 12:23

풀이

MST로 풀 수 있는 문제이다. 문제는 도시에서 절약할 수 있는 최대 액수를 구하는 것이고 이는 최소 액수로 가로등을 키는 문제라고 생각할 수 있다. 따라서 kruskal 알고리즘을 통해 가로등을 키는데 필요한 비용을 계산하고, 전체 비용에서 빼주면 된다.

코드

C++

Python3