wiz   1년 전

이분매칭으로 풀었는데 시간초과가 납니다.

각 정점마다 a부터 b번까지의 간선을 모두 추가해야 하는데, 연결된 간선이 너무 많아서 그런 것이 아닌가 추측됩니다.

혹시나 다른 방법을 알고 계시면 답변 부탁드립니다.

yukariko   1년 전

저는 정렬후에 O(N)으로 총 O(NlgN)으로 풀었습니다.

hakgb11   1년 전

이렇게 수정하니 답이 나왔습니다.

wiz   1년 전

답변들 정말 감사합니다.

좀 더 배워갑니다.~

luke0201   1년 전

참고로 말씀드리자면 네트워크 플로우 알고리즘은 시간 복잡도가 꽤 큽니다. 그래서 보통 N이 200 정도로 주어지니까 이 이상인 경우에는 다른 방법을 생각해보심이 ㅎ.

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