ness9917   1년 전

코사라주 알고리즘을 이용해서 풀어보았는데요,

그래프를 scc그래프로 변환하고,

위상정렬 후에

시작지점이 있는 scc컴포넌트로부터 dp를 이용해서 최댓값을 구했습니다.

게시판 반례들은 모두 통과합니다.

반례 부탁드립니다 ㅠㅠ

zenith82114   1년 전

scc들에 대해서 in-degree를 재려고 하신 것 같은데

지금 in값이 커지는 기준이 원래 그래프의 간선으로 되어 있습니다.

다시 말하면, 한 scc에서 다른 scc로 가는 (원래 그래프상의) 간선이 여러 개여도 하나로 세야 하는데

다 따로 세기 때문에 topo 벡터가 잘못 만들어집니다.

zenith82114   1년 전

추가로 팁을 드리자면, 코사라주 알고리즘을 쓰면

두 번째 DFS에서 scc들에 번호가 붙여지는 순서가 곧 scc들의 위상정렬된 순서이기 때문에

굳이 다시 안 해줘도 됩니다.

ness9917   1년 전

아이고 감사합니다..

위상정렬을 굳이 해줄필요도 없었군요 새로운 사실을 알아갑니다,,

 + 위에 반례는 정답이 27이 아니라 25네용

zenith82114   1년 전

아 맞습니다 처음에 9개짜리로 했다가 2개 뺀 거라서..

powerlsj7   1년 전

예제 도움 받았습니다. 감사합니당

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