14216번 - 할 일 정하기 2
그냥 최소비용 최대유량으로 푸는거라 생각하고 풀었습니다. SPFA알고리즘 썼습니다. 그런데 바로 시간초과가 나네요. 그냥 될 줄 알았는데..
더 빠른 알고리즘이 있는건가요? 아니면 최적화를 할 수 있는 부분이 따로 있는건가요?
haja 님 감사합니다. 헝가리안이 V(n^3)이래서 0.5초만에 안 돌아갈 것 같아서 안봤는데.. 한번 찾아봐야겠네요!
사실 저도 공부를 안해서요..
haja ㅠㅠ 어쨌든 감사합니다. 잘 찾아볼게요!
http://koosaga.myungwoo.kr/ent...
여기 글이 도움이 될 것 같네요
https://www.topcoder.com/commu...
haja 님 늦은시간까지 정말 감사합니다ㅠㅠ 위 링크 들어가서 보니 cycle canceling으로 MCMF를 O(n^3)까지 줄일 수 있다는 부분 말씀하신거 같아서 찾아보고 있었습니다. 해석이 안돼서 좀 느리지만..ㄱ= 다시 감사드립니다ㅠㅠ
댓글을 작성하려면 로그인해야 합니다.
ehddml3 7년 전
그냥 최소비용 최대유량으로 푸는거라 생각하고 풀었습니다. SPFA알고리즘 썼습니다. 그런데 바로 시간초과가 나네요. 그냥 될 줄 알았는데..
더 빠른 알고리즘이 있는건가요? 아니면 최적화를 할 수 있는 부분이 따로 있는건가요?