앳코더 라이브러리에 있는 mincostflow 쓰려고 하는데 거기선 MCMF 구하는게 F(n+m)log(n+m)이더라 와우
원래는 Fnm 흑마술 SPFA 써야 F(n+m)이 되잖어 SPFA는 쓸때 찜찜하기도 하고
그런데 ACL에서는 cost가 항상 0이상이여야 된다는 조건이 붙는단 말이지.
혹시 cost가 항상 0이상이면 왜 MCMF를 F(n+m)log(n+m)만에 구할 수 있는지 아는 분 있음?
최단거리를 다읷으로 찾아서 그런가 싶기도 한데 음수간선 있으니 다읷도 안되잖아
코드를 보진 않았지만 potential function쓰면 다익으로 할수있음. 비용 음수 있으면 처음에 벨만포드 한번 돌리고 하면 됨
이해가 잘 안가네... potential function이 뭐야?
대충 소스에서 최단경로를 d(u)라 하면 u -> v 가중치 w 간선의 가중치를 w + d(u) - d(v)로 바꾼다고 생각하면 됨
뭐지 A* 비슷한건가? 함 내가 더 찾아봄 ㄱㅅㄱㅅ
primal-dual method인데 johnson's algorithm 찾아보면 이해하기 편할듯 - dc App
ACL 라이브러리 뜯어보니 듀얼 어쩌구 얘기 있는거보면 이 method 맞는듯. 찾아봄 모두 ㄳㄳ