H. Networks with Unidirectional Links

ProblemH_Eng.pdf

전형적인 이분매칭 문제다.

대회 끝나고, 단순히 '매칭'이라고만 들었을 때는 전혀 와닿지 않았고 해법이 떠오르질 않았다. 그래프를 어떻게 구성해야되는 것이며 그래프를 어떻게 구성해야되는 것이며... 머리 속이 복잡했다.

우선 이분 그래프의 양쪽에 0번 부터 $N-1$번까지 노드들을 총 $2N$개 만든다. i번 노드에서 j번 노드로 가는 방향성 에지가 있으면 이분그래프에서 왼쪽 i번 노드에서 오른쪽 j번 노드로 뻗는 간선을 그어준다.

그 뒤 최대 매치수가 곧 답이다.

이 방법으로 답이 나오는 이유에 대한 자세한 설명은 생략한다.

포트퍼거슨으로 짜도 시간안에 나올 수 있다. 하지만, Hopcroft-karp 알고리즘을 통해 최악에 $O(M \sqrt{N})$의 시간복잡도로 풀 수 있으며, 평균 시간복잡도 $O(M \log_2 N)$에 문제를 해결할 수 있다. 

** 코드에 틀린 부분이 있어 수정했습니다. (10/2 17:00)

H.cpp