디닉 알고리즘 (Dinic's Algorithm)

네트워크 플로우 포드풀커슨 \(min(O(Ef),O(VE^2))\)

네트워크 플로우 디닉 \(O(V^2E)\)

1. 잔여용량이 존재하는 간선을 따라 BFS하면서 정점들의 level을 매겨준다. s가 level 0

- t의 level이 정해지지 않는다면 더 이상 증가경로는 없음. (현재 유량이 최대 유량)

2. s부터 DFS하면서 t에 도달할 때 까지 항상 level[u]+1==level[v] 를 만족하는 edge만 따라서 이동한다.

- DFS 종료 하면서 유량 갱신해주고 더 이상 증가경로가 없을 때 까지 반복한다.

- DFS 시 추가적으로 현재 몇 번 간선까지 사용하였는지 저장하는 배열을 이용해서 불필요한 탐색을 줄인다.

3. 더 이상 증가 경로가 없다면 1.로 돌아간다.