[일반] G어케푸는거?

[익명(182.231)]

에디가 안올라와...

- dc official App

[익명(223.39)]

위상정렬 순으로 DP 풀었음

[익명(223.39)]

각 노드마다 기본 큐트값이 1이고, 초기 out이 2 이상이어야 다음 노드로 큐드값을 전달 가능하고 초기 in이 2이상이어야 그 cute값 받아와서 +1 한걸 가질 수 있다고 풀었음 그런식으로 최대 유지하는식으로 해서 최대값 찾는식으로 했음

[EN_SA(encludingsalt)]

왜그게성립하는지모르겟서요...

[EN_SA(encludingsalt)]

아

[익명(223.39)]

뭔가 쓴거랑 풀이가 같았는지 긴가민긴한데, 아무튼 저런 느낌의 로직이었어

[익명(223.39)]

어차피 cute한 집합은 그래프상에서 하나의 경로로 존재하고 in/out이 1인 경우는 반드시 지워져야해서 없는거랑 마찬가지여서 전달을 주고받지 않아

[익명(182.231)]

아 내가 cute한 집합의 정의를 잘못이해하고 있었네 남은 component크기 중 최댓값인줄 알았는데 그럼 모순인 경우가 있네 무조건 path만 되는구나 - dc App

[익명(182.231)]

이해됬다 ㄱㅅㄱㅅ - dc App

[익명(223.39)]

일단 그래프가 DAG이기도 하고, cute 내에 어떠한 두 쌍 u,v에 대해서 u->v 이거나 v->u 인 직간접적인 경로가 존재해야하는데 하나의 경로가 아닌 트리모양처럼 되면 위에 해당하지 않는 노드쌍이 생길거야

[익명(182.231)]

말해준대로 짜서 통과됬는데 뭐지 구현 실수하셨나봄 - dc App

[익명(223.39)]

아 업데이트 실수했음 ㅋㅋㅋㅋ