p_ce1052   3일 전

이 문제가 디닉을 써야만 하는 문제로 나와있는데

디닉 알고리즘의 시간복잡도가 O(V^2 * E)인 것으로 알고 있습니다.

위 문제에서 간선이 대충 10만개라고 해도 25만 * 10만을 하면 너무 커지지 않나요?

네트워크 플로우 관련 문제들을 보면서 느끼는게 시간복잡도를 구하는게 너무 힘드네요 왜 디닉 알고리즘을 사용하면 시간복잡도가 맞는지 설명해주실 수 있나요? 

댓글을 작성하려면 로그인해야 합니다.