jungin0507   3년 전

에드몬드-카프 알고리즘이나 MCMF 알고리즘은 시간복잡도가 O(|E|f)라고 알고있습니다.

이 문제에서 최대 유량은 Ai의 최댓값 100 * N의 최댓값 100을 해서 최대 10000까지 나올 수 있고,

Edge의 개수는 노드의 개수가 N + M + 2(source, sink)이므로 (N+M)^2 이고 이는 최대 40000까지 가능합니다.

그래서 O(|E|f)를 보았을때 40000 * 10000을 해서 최대 4억번의 연산이 이루어진다? 라고 말할 수 있는것같은데 시간초과가 나지 않는 이유가 궁금합니다.

djs100201   3년 전

에드몬드 카프 알고리즘의 시간복잡도는 O(VE^2)입니다.
O(|E|f)의 시간복잡도를 갖는 알고리즘은 dfs를 이용한 포드풀커슨 알고리즘입니다.

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