opop20207   4년 전

최근 플로우 공부한다고 디닉을 배웠습니다.

곧바로 이문제에 적용해봤는데요

에드몬드 카프는 1200ms정도에 통과했는데

https://www.acmicpc.net/source/15677487

디닉은 72ms밖에 안걸리더라구요

https://www.acmicpc.net/source/15677353

시간복잡도가 디닉이 O(V^2 * E), 에드몬드 카프가 O(V * E^2)으로 알고있는데 이렇게 차이가 많이 나는가요?

이분그래프같은 특수한 경우가 아니면 가장 빠른 알고리즘이라고는 했지만 이렇게 파워풀한줄은 몰랐습니다.

아니면 제가 에드몬드 카프를 잘못짠건가요? 시간이 저렇게 나오면 안된다던지...

시간차이가 제가 생각했던거보다 훨씬 많이 나서 질문드립니다.

조언 주시면 감사하겠습니다.

jhnah917   4년 전

이 문제는 정점 약 n개, 간선 약 n^2개로 구성된 그래프에서 플로우를 돌립니다.

V = n, E = n^2로 잡으면 에드몬드 카프는 O(n^5), 디닉은 O(n^4)이므로 그 정도의 시간 차이가 날 수 있다고 생각합니다.

opop20207   4년 전

E는 많이 잡아야 5n개 정도 아닌가요?

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