madpota   3년 전

저는 m 개의 간선들을 union 에 미리 포함시키는 대신

해당 간선들의 가중치를 0으로 만든 다음 일괄적으로 kruskal 돌렸습니다

최소 가중치는 음수가 나올수 없으므로 그렇게 해도 동일한 효과가 나오니까요.

그런데 바로 오답 뜨길래 질문 글 찾아보니 가중치 계산과정에서 범위 초과가 나올수 있다길래

제곱 하는 부분을 다소 수정하였지만, 계속 9%를 못넘기네요.

가중치 구하는 부분(dist)가 문제인지, 아니면 처음부터 생각이 잘못된 건지 감이 안가네요.

kdh9949   3년 전

이미 주어진 간선의 가중치를 0으로 만드는 아이디어는 맞을 텐데, 구현에서 실수하신 것 같습니다.

3 2
1 1
1 2
1 3
1 2
1 3

이 데이터에서 0.00이 나오지 않고 1.00이 나옵니다. (1-2, 1-3 간선을 이미 주었으므로 더 간선을 만들 필요가 없음)

madpota   3년 전

already 부분이 잘못됐네요

감사합니다

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