2e718   8년 전

이렇게 질문을 올리는게 나중에 스포가 되는 것이 아닌가 조심스럽네요.


먼저 이 문제에 대한 접근은 total flow가 2인 minimum cost flow를 구하는 것이라고 생각하였습니다.

그렇기 때문에 처음에 벨만포드를 이용하여 최단경로를 구한 뒤,


포드-풀커슨 알고리즘과 비슷한 방식을 이용하여

a->b로 갔다면 다시는 a->b로 갈 수 없으므로 edge의 weight를 INF로 처리하여 다시는 방문하지 않도록 하였으며,

b->a로 가는 edge의 경우 weight에 -1을 곱했습니다.

왜냐하면 첫번째 flow에서 a->b->c->d와 같은 경로가 있고, 두번째 flow에서 a->c->b->d와 같은 경로가 있다고 가정하면,

이 두 경로에서 나오는 cost보다 a->b->d와 a->c->d에서 나오는 cost가 더 적은 것이 자명하며, 결국 b-c edge는 방문하지 않은 것이나 마찬가지로 생각하기 위해서입니다.


이렇게 edge를 처리한 뒤 두 번째 flow를 위해 한번더 벨만포드를 이용하여 cost를 구한 뒤, 이전의 cost와 합하여 답을 출력하도록 하였습니다.

mcmf이지만 모든 edge의 capacity가 1이므로 어차피 한 번 지나간 경로의 weight를 INF로 설정하면서 굳이 capacity나 flow에 대한 고려는 안해도 된다고 생각하였습니다.


하지만 번번이 WA를 받아서 제가 무엇을 고려하지 못하고 있는 것인지 알고 싶습니다.

혹시 일반적인 단방향 그래프의 mcmf가 아니라 양방향 그래프이기 때문인지, 단순그래프라는 보장이 없기 때문인지, 아니면 제가 생각하고 있는 방법 자체가 잘못됐거나 포드풀커슨의 방법을 이용하는 중간에 문제가 있었는 지 알고 싶어 이렇게 글을 쓰게 되었습니다. (사실 단순그래프인지 여부는 코드를 약간 수정하여 제출하여 확인해보았는데 아닌 것 같긴 하지만 불확실합니다.) 제출하자마자 거의 바로 WA가 나와서 아마 거의 처음부터 틀리는 것 같지만 제가 짠 알고리즘이 왜 틀리는 지를 알게 되어 공부에 도움이 되었으면 합니다.

jh05013   6년 전

1년 된 글이지만, 저도 반 년 넘게 WA의 늪에 있었던 문제라서 (지금도 WA...) 글을 남깁니다.

단순그래프가 아닙니다...

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