Dinic - Network Flow (Maximum Flow)
오늘 드디어 디닉 알고리즘을 정복했다. 작년 입사시험 보기전에서티 기출로 네트워크 플로우 문제가 나왔다고 해서디닉까지 준비해서 가려고 했었는데,그때부터 지금까지 준비한다고 말만하다가 1년도 더 지난 오늘에서야 공부하게 됐다 ㅠ 시간복잡도는 O(V^2 E)이지만 이것보다 훨씬 빨리 동작하며, 거의 O(VE)로 봐도 무방할만큼의 속도를 보여준다.사실상 PS문제에서 Network Flow문제가 제한에 대해 최악의 경우까지 가도록 테케를 만드는건 거의 불가능(?)하기 때문에... 아무튼 생각보다 훨씬 쉬웠다.역시 지금까지 공부한 알고리즘 중에서 LCP가 제일 익히기 까다로웠는데,그에 비하면 디닉은 아주 쉬웠다. 간단하게 말하자면 bfs돌면서 정점들의 level을 체크해주고,level체크가 완료되면 network..
