wiz   1년 전

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

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

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

yukariko   1년 전

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

hakgb11   1년 전

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

wiz   1년 전

답변들 정말 감사합니다.

좀 더 배워갑니다.~

luke0201   1년 전

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

myth   2달 전

wiz 님 어떻게 풀이를 변경하셨는지요?

DFS 함수 내만 변경된 것 같은데.... 맞는지요? 

@yukariko 님 그리디로 어떻게 하는지 도움을 주실 수 있을까요?


yukariko   2달 전

1년전 풀이라 제 코드를 봐도 무슨생각으로 이렇게 했는지 모르겠네요..

무엇보다 O(N)도 아니었고, 제 풀이가 정답인지도 모르겠습니다.

일단 코드 첨부하겠습니다.

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