hellogaon

디닉 알고리즘(Dinic's Algorithm)은 더 빠른 시간복잡도의 최대 유량 알고리즘으로네트워크 유량의 기본 알고리즘인 포드-풀커슨 알고리즘의 시간복잡도는정점 개수가 V 간선 개수가 E이며 문제의 답이 f일 때 min(O(Ef), O(VE^2))이였으나디닉 알고리즘의 시간복잡도는 O(V^2E)입니다.이 알고리즘에서 아래와 같은 새로운 용어를 사용합니다. 레벨 그래프(Level Graph) : 모든 정점에 대하여 소스로부터 거쳐야하는 최소 간선 수를 값으로 가지는 그래프(이 때 여유 용량이 있는 간선만 사용가능)차단 유량(Blocking Flow) : 레벨 그래프 상에서 인접하면서 자신보다 레벨이 1 큰 정점으로만 흐를 수 있을 때소스에서 싱크로 흐를 수 있는 최대 유량 이후 동작원리는 아래와 같습니..