도시 분할 계획1

• 

  백준 - 1647 도시 분할 계획 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 풀이 방법 이전에 풀었던 1922 네트워크 연결 문제와 아주아주아주 동일한 문제 사실 가장 큰 차이점은 마을을 두개로 분리했을 때 도로 최소 유지비용을 찾는 것이다. 이 문제에서 가장 고민했던 부분이 바로 저 부분이었다. 최소 신장 트리를 만들어서 하는 것은 알겠는데...대체 어떻게 두개로 나누지...? 그리고 두개로 나눈 후 어떻게 최소 유지비용을 찾지..?.. Java - 알고리즘 2022. 8. 27.