kks227   1년 전

최소 스패닝 트리와 최대 스패닝 트리의 cost를 구해서 푸는 문제가 아닌가요?

뭔가 사소한 실수가 있는 것일까요...

N, M이 입력보다 실제로 1 많다는 것도 처리했는데...

문제에서 "필요한 최소한의" 경로만 사용한다고 했으므로 최악의 경우도 스패닝 트리는 맞을 텐데...

alohajihwan   1년 전

문제를 잘 읽어 보시면 w 가 0일때 오르막길 입니다. 따라서 구조체 sort할 때 w > O.w 로 고쳐 주어야 하며

r1 += (e[i].w == 0) 으로 수정해주면 맞았습니다가 뜹니다.

kks227   1년 전

감사합니다. 그냥 오름차순 정렬하고 cost를 그대로 더하면 될 줄 알았는데 예제만 되는 거였군요.

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