개발조아

문제 링크 : https://www.acmicpc.net/problem/23034 23034번: 조별과제 멈춰! 교수님이 시험 기간에 조별 과제를 준비하셨다...! 가톨릭대학교의 조교 아리는 N명의 학생을 2개의 조로 구성하여 과제 공지를 하려 한다. 이때, 구성된 각 조의 인원은 1명 이상이어야 한다. 각 www.acmicpc.net MST와 BFS로 풀었다. 처음에는 단순하게 MST 구성해서 가중치 합 구하고 x,y의 간선 정보만을 보고 빼주면 될줄 알고 제출했더니 틀렸다. 당연하다. 문제는 두개의 점을 기준으로 두개의 MST를 만드는 것이다. 그래서 모든점을 포함하는 MST를 구성하고, 두 점을 기준으로 두개의 MST로 나누어야한다. 따라서 두 점 사이의 간선 중 가중치가 가장 큰 것을 빼주면 두개..