clumpy   11달 전

98% 에서 실패하였습니다.

정확히는 잘 모르겠지만,

(1) 0  ~ n-2 까지 MST를 찾아서 2개의 그룹으로 분할하는 방식은 반례가 존재하는 것 같습니다.

(2) 0 ~ n-1 까지 MST 를 찾은 후에 가장 비싼 길 1개를 제거하여 계산하니 100% 성공하였습니다.

저와 유사한 오류 있으신 분 계실 것 같아 글 남깁니다. 감사합니다.

zenith82114   11달 전

(1)번 방법으로도 정답을 받을 수 있습니다. 구현을 잘못하신 것입니다.

댓글을 작성하려면 로그인해야 합니다.