티스토리 뷰

이분매칭 포드 풀커슨  \(O(VE)\)

이분매칭 호프크로프트 카프  \(O(\sqrt{v}E)\)



a->b 형태로 매칭 한다고 하였을 때.


1. 매칭되지 않은 a 정점을 level 0으로 하여 bfs 한다.  


2. b정점이 매칭되어 있고 (matched_b[b]!=-1) 

    해당하는 a 정점의 level이 정해지지 않았다면 (level[matched_b[b]]==-1)

    해당 정점의 level을 갱신한다. (level[matched_b[b]]=level[a]+1)


3. 매칭되지 않은 모든 정점에서 dfs 한다. b정점이 매칭되지 않았거나, 

    매칭된 a정점의 level이 현재 정점 level+1이라면 새로운 증가경로를 탐색한다.

    (matched_b[b]==-1||(level[matched_b[b]]=level[a]+1&&dfs(matched_b[b])))



'Algorithm' 카테고리의 다른 글

문제 해결 전략  (0) 2017.04.24
복잡도 분석  (0) 2017.04.24
디닉 알고리즘 (Dinic's Algorithm)  (0) 2017.04.03
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함