Hopcroft-Karp (호프크로프트 카프)
코드
정리
- 이분 매칭 문제를 O(sqrt(V)*E) 의 시간복잡도로 해결할 수 있다.
- 이분 그래프는 E의 최악이 V^2 이므로 약 O(V^2.5) 의 시간복잡도이다.
- 모든 용량이 1인 이분 그래프인 환경으로 국한해서 만든 알고리즘 = 디닉 + 이분매칭의 느낌
- 교차경로(alternating path) : 매칭이 주어질 때, 매칭에 속한 간선과 안속한 간선이 번갈아가며 나타나는 경로 (이때 경로의 양 끝은 매칭에 속한 간선이어야 한다), 모든 매칭을 다 포함하지 않아도 된다
- 증가경로(augmenting path) : 매칭이 주어질 때, 매칭에 속한 간선과 안속한 간선이 번갈아가며 나타나는 경로, 양 끝은 매칭에 속하지 않아도 된다. 모든 매칭을 다 포함하지 않아도 된다
- 증가경로를 찾은 뒤, 매칭 여부를 반전시키면, 매칭 수가 1증가한다. (증가경로를 반전시킴으로써 매칭수를 1 증가 시킬 수 있다)
- 호프크로프트 카프
- 매칭 M 이 공집합인 상태로 시작한다.
- 서로 정점, 간선이 겹치지 않는 증가 경로의 집합 P를 찾는다
- M = M xor P
- P 가 공집합이면 종료하고, 아니면 2로 돌아가 반복한다.
- 구현
- 레벨이 0인 정점을 정한다 (A그룹에 속해있고, 매칭에 속하지 않은 정점)
- BFS 를 하여 다른 정점들의 레벨을 매긴다. 다른 정점은 레벨 0 정점과의 최단거리 중 최소값
- 디닉 알고리즘 처럼 1 증가하는 순으로만 정점을 거친다.
- 만약 증가 경
관련 문제
https://www.acmicpc.net/problem/3736 (System Engineer)