개발일지

개념 이분 그래프가 있을 때 A집합과 B집합을 최대한 매칭하는 경우 Alternating Path(교차 경로) 그래프 위의 경로 중 매칭되지 않은 정점부터 시작하여 매칭을 이어주고 있지 않은 간선과 이어주는 간선이 교차하면서 반복되는 경로 (X - O - X - O - X ....) (X : 연결안된 정점, O : 연결된 정점) Augmentine Path(증가 경로) 양 끝 정점이 매칭되어 있지 않은 교차경로 교차경로 안에서 증가경로를 반전하면 매칭의 크기를 늘릴 수 있다. 작동원리 1. A그룹에서 매칭에 속하지 않은 정점들의 레벨을 구한다. 2. 증가 경로를 체크한다. 3. 더 이상 증가경로를 찾지 못할 때까지 반복한다. 시간복잡도 O(V^(1/2) * E) 문제 9525 룩 배치하기 www.acmi..