Dinic algorithm (디닉)
코드
정리
- 시간복잡도 O(V^2*E), 애드몬드 카프보다 빠르다.
- 레벨 그래프(level graph) : 모든 정점에 대해 소스에서부터의 최단거리를 레벨 값으로 매겨놓은 그래프, 여유 용량(residual)이 없는 간선은 사용할 수 없다.
- 차단 유량(blocking flow) : 레벨 그래프에서는 간선 u, v가 존재하더라도 v의 레벨이 u의 레벨보다 1 클때에만 이동 가능하다. 이런 그래프에서 더 이상 소스에서 싱크로 흘릴 수 있는 유량이 없게 만드는 유량 상태
- 디닉 알고리즘 (아래의 작업을 반복)
- 레벨 그래프를 만든다. 싱크에 도달할 수 없다면 종료한다.
- 레벨 그래프에서 차단 유량을 찾아 그만큼을 총 유량에 더한다.
관련 문제
- https://www.acmicpc.net/problem/13161 : 분단의 슬픔
- https://www.acmicpc.net/problem/6241 : Dining