ehddml3   7년 전

그냥 최소비용 최대유량으로 푸는거라 생각하고 풀었습니다. SPFA알고리즘 썼습니다. 그런데 바로 시간초과가 나네요. 그냥 될 줄 알았는데..

더 빠른 알고리즘이 있는건가요? 아니면 최적화를 할 수 있는 부분이 따로 있는건가요?

haja   7년 전

헝가리안 메소드를 사용할 수 있을 것 같습니다.

ehddml3   7년 전

haja 님 감사합니다. 헝가리안이 V(n^3)이래서 0.5초만에 안 돌아갈 것 같아서 안봤는데.. 한번 찾아봐야겠네요!

ehddml3   7년 전

haja 님 혹시 헝가리안 메소드에 대한 설명이 잘 되어있는 곳을 추천해주실 수 있나요..? 설명이 잘 되어있는 곳을 찾기가 어렵네요ㅠㅠ

haja   7년 전

사실 저도 공부를 안해서요..

ehddml3   7년 전

haja ㅠㅠ 어쨌든 감사합니다. 잘 찾아볼게요!

haja   7년 전

http://koosaga.myungwoo.kr/ent...

여기 글이 도움이 될 것 같네요

ehddml3   7년 전

haja 님 늦은시간까지 정말 감사합니다ㅠㅠ 위 링크 들어가서 보니 cycle canceling으로 MCMF를 O(n^3)까지 줄일 수 있다는 부분 말씀하신거 같아서 찾아보고 있었습니다. 해석이 안돼서 좀 느리지만..ㄱ= 다시 감사드립니다ㅠㅠ

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