디닉

디닉 알고리즘(Dinic's Algorithm)은 더 빠른 시간복잡도의 최대 유량 알고리즘으로

네트워크 유량의 기본 알고리즘인 포드-풀커슨 알고리즘의 시간복잡도는

정점 개수가 V 간선 개수가 E이며 문제의 답이 f일 때 min(O(Ef), O(VE^2))이였으나

디닉 알고리즘의 시간복잡도는 O(V^2E)입니다.

이 알고리즘에서 아래와 같은 새로운 용어를 사용합니다.

레벨 그래프(Level Graph) : 모든 정점에 대하여 소스로부터 거쳐야하는 최소 간선 수를 값으로 가지는 그래프

(이 때 여유 용량이 있는 간선만 사용가능)

차단 유량(Blocking Flow) : 레벨 그래프 상에서 인접하면서 자신보다 레벨이 1 큰 정점으로만 흐를 수 있을 때

소스에서 싱크로 흐를 수 있는 최대 유량

이후 동작원리는 아래와 같습니다.

1. 레벨 그래프를 생성한다. 싱크에 도달 할 수 없으면 종료한다.

2. 레벨 그래프에서 차단 유량을 찾은 뒤 흘려 보낸다.

3. 1번과 2번 동작을 반복한다.

이 알고리즘을 이용하여 최대 유량을 빠르게 구할 수 있습니다.

기본 문제

13161번: 분단의 슬픔