canplane   3년 전

정점 가중치가 0보다 크기 때문에, 임의 정점에 대하여 어떠한 우수 마을도 인접하지 않는 경우는 없습니다.

조건 1에 따르면, 어떤 정점 v가 우수 마을이 아니고 v와 인접한 모든 정점들 w 역시 우수 마을이 아닌 상태라면, v를 추가로 우수 마을로 선정할 수 있기 때문입니다.

따라서 각 w 서브 트리들에서 w를 선정하지 않은 경우가 선정한 경우보다 더 큰 경우가 된다면, 이들을 포함한 v 서브 트리에서는 무조건 v를 우수 마을로 선정한 것이 그렇지 않은 경우보다 크게 됩니다.

따라서 조건 3은 자동으로 따라오는 성질입니다.

minbud   3년 전

감사합니다 근데 만약 정점 가중치가 음수인 경우도 있어서 조건3을 따로 체크를 해줘야한다면 코드로 어떻게 구현해야 되나요??

어떻게 구현이 가능한지 감이 전혀 안잡힙니다.

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