인프라 엔지니어가 꾸는 꿈

문제 링크 한 마을은 N개의 집과 m개의 도로로 구성되어 있습니다. 각 집은 0번부터 N-1번까지의 번호로 구분됩니다. 모든 도로에는 가로등이 구비되어 있는데, 특정한 도로의 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일합니다. 예를 들어 2번 집과 3번 집 사이를 연결하는 길이가 7인 도로가 있다고 해봅시다. 하루 동안 이 가로등을 켜기 위한 비용은 7이 됩니다. 정부에서는 일부 가로등을 비활성화하되, 마을에 있는 임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈 수 있도록 만들고자 합니다. 결과적으로 일부 가로등을 비활성화하여 최대한 많은 금액을 절약하고자 합니다. 마을의 집과 도로 정보가 주어졌을 때, 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력하는 프로그램을 ..

문제 링크 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 Test Case 문제 풀이 그래프 문제 중 크루스칼 알고리즘. 전체 그래프에서 2개의 최소 신장 트리를 만들어야하는데, 제일 좋은 방법은 일단 주어진 그래프를 최소 신장 트리로 만들고, 그 중에서 제일 비용이 큰 마을 사이를 빼면 문제 조건을 만족할 수 있다. 서로소 집합 개념과 크루스칼 알고리즘을 알아야 풀 수 있고 find_parent, uni..