[BOJ C++] 1647 도시 분할 계획

https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

 

 

문제 이해

단방향 그래프가 주어지면 해당 그래프의 간선들을 지워 2개의 다른 그래프로 만들어야 했습니다. 하지만 각각의 그래프는 모두 연결되어 있어야 하며 간선의 가중치의 합이 가장 적도록 하는 문제였습니다.

 

 

입출력 조건

시간초 제한 2초, 정점의 수는 최대 100,000개까지 가능했습니다.

 

 

풀이

모두 연결되어 있으면서 간선의 가중치들의 합이 가장 작아야 한다는 것은 결국 최소 스패닝 트리를 구하는 문제였습니다.

하지만 2개의 그래프로 나눠야 한다는점에서, 그냥 최소 스패닝 트리를 구하고, 가장 큰 간선 하나를 짜르면 되는 것 아닌가 라고 생각했는데 맞았습니다....단순한 최소 스패닝 트리 문제였습니다.

 

 

에러 및 느낀 점

.

 

 

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/1674_%EB%8F%84%EC%8B%9C%20%EB%B6%84%ED%95%A0%20%EA%B3%84%ED%9A%8D.cpp

GitHub - JuneYoungDo/Algorithm: This is a repository for additional problem solving in Baekjun.