알고리즘 (16) 썸네일형 리스트형 디닉의 알고리즘 Dinic's Algorithm 대표적인 최대 유량 알고리즘이다. 정점의 개수를 $V$, 간선의 개수를 $E$, 최대 유량(답)을 $f$라 할 때, $O(fE)$ 또는 $O(V^2E)$에 동작한다. 간선의 유량이 모두 같을 경우(모두 0 또는 1), 신기하게도 $O(min(V^{2/3}E, V^{3/2}))$에 동작한다. 직접적인 flow문제는 별로 없고, 최댓값을 구하는 문제를 max flow로 환원할 수 있는 경우가 종종 있다. 혹은 최솟값을 구하는 문제를 min cut으로 환원하기도 한다. 아래 링크들을 보고 공부하였다. https://jason9319.tistory.com/150 https://koosaga.com/18 https://koosaga.com/133 내 코드 #include using namespace std; #d.. 이전 1 2 다음