테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 최소 비용 최대 유량 (MCMF, Minimum Cost Maximum Flow) ======

[작성중]

===== 알고리즘 =====
  * Successive shortest path 
    * (=capacity scaling ??)
    * 가장 널리 쓰이는 방법. 포드풀커슨 알고리즘과 비슷한 원리로, Shortest path를 찾고, 그 패스에 플로우를 할당하는 것을 반복한다
    * 음수 엣지가 존재하므로, 최단경로를 찾을때에는 벨만-포드나 SPFA를 써야 한다. 따라서 최단 경로를 한번 찾는 시간복잡도는 O(VE)
      * 벨만포드는 O(VE)지만, SPFA는 최악 O(VE), 평균 O(E)이다. 일반적인 최단경로 문제를 풀때에는 저격 데이터들도 많고 해서 SPFA도 그냥 O(VE)고 벨만포드와 큰 차이가 없다고 생각했지만 MCMF처럼 최단경로 계산을 반복적으로 해야하는 상황에서는 벨만포드보다 확실히 메리트가 있는듯 하다
    * O(f)만큼 최단경로 찾는것을 반복해야 하므로 최종 시간복잡도는 O(fVE)로 알려져있다.
      * [[https://cp-algorithms.com/graph/min_cost_flow.html]] 에서는 에드몬드-카프 알고리즘과 같은 형태이므로 O(VE)번만 최단경로를 찾으면 된다고 한다. 그러면 O(V^2E^2) 인데.. 국내 다른 자료에서는 이렇게 쓰여있는것을 본적이 없어서 확인이 좀 필요하다.
  * zkw MCMF 
    * Dinic 알고리즘과 비슷하게, level 그래프를 만들고 유량을 흘리는 방식이 가능하다고 한다.
    * [[https://justicehui.github.io/hard-algorithm/2020/03/24/effective-mcmf/]] 참고
    * 시간복잡도 자체가 줄어드는거는 아닌거 같고, 그냥 약간의 커팅인듯.. sparse 그래프에서 빠르게 작동한다고 한다
  * Johnson’s Algorithm
    * (=Cycle Canceling ?)
    * 그래프에서 최단 경로를 유지하면서 negative 엣지를 없애주는 알고리즘이다. 이 알고리즘을 사용해서 negative edge를 없애주면, 최단 경로를 다익스트라 알고리즘으로 O(ElogV) 또는 O(V^2) 에 구할수 있다
    * 그러면 MCMF의 총 시간복잡도가 O(fElogV) 이나 O(fV^2) 으로 단축되긴 한다.
  * Push relabeling (=Cost Scaling)
    * [[https://koosaga.com/289]]
    * O(V^3log(VC))

  * 최소 비용 이분 매칭
    * 헝가리안 알고리즘