dotorya   1년 전

음.. 이 문제는 다들 이분매칭으로 푸는 것 같은데

일반적인 경우에 1000^3이 시간초과가 나지 않나요?

일반적으로 이분매칭의 시간복잡도가 O(Ef)고, 다음과 같은 데이터에서는 E ~ V^2, f~V가 되어 시간이 초과되어야 할 것 같습니다.

실제로 제 AC된 소스에서도 이 데이터는 Release모드로 10초 가까이 걸리더군요..


1000

1 1 1

2 2 2

....

1000 1000 1000


이런 문제가 있어 N제한을 줄이고 데이터를 보강할 필요가 있지 않을까 합니다.

최악의 경우 O(N^3) 알고리즘이 N = 1000인데도 0ms에 나오는거에 좀 놀랐습니다.

appa   1년 전

실제 데이터는 N이 100이하인 것 같습니다.

그리고 Hopcorft-Karp나 Dinic으로 플로우를 돌릴 경우, N이 1000이더라도(말씀하신 데이터를 넣었는데) 1초 내에 나오네요.

dotorya   1년 전

감사합니다! 좀더 빠른 flow 알고리즘들을 구현해봐야겠네요..

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