Bipartite Matching2 이분 매칭 (Bipartite Matching) Contents 이분 매칭 (Bipartite Matching) 백준 2188 : 축사 배정 선형 계획법과 치환 (2) - Network Flow, Bipartite Matching 위 포스팅에서 네트워크 유량과 이분 매칭에 대해서 알아봤었는데, 이번 포스팅에서는 이분 매칭을 어떻게 구현하느냐에 초첨을 맞추어 보려고 합니다. 지난 포스팅에서 이분 매칭은 최대 유량(maximum flow) 문제로 치환되어 선형 계획법을 사용할 수 있다고 했었는데, 즉, 최대 유량 문제를 풀듯이 풀 수 있다는 것 입니다. 위에서 소년들과 소녀들을 매칭하는 문제에서, 위의 그래프처럼 모든 소년들을 향해 나가는 간선들을 갖는 새로운 source 노드와 모든 소녀들로부터 들어가는 간선들을 갖는 새로운 sink 노드 t를 만들고,.. 2022. 4. 21. 선형 계획법과 치환 (2) - Network Flow, Bipartite Matching References Algorithm (Sanjoy Dasgupta) Contents Flows in networks Max-flow Min-cut Theorem Bipartite Matching (이분 매칭) 선형 계획법과 치환 (1) - Examples of LP 선형 계획법과 치환 (1) - Examples of LP References Algorithms (Sanjoy Dasgupta) Contents Introduction to Linear Programming Reduction (치환) Simplex Method 최단 경로나 최소 비용 신장 트리(cheapest spanning tree), 최장 증가 부분 수열(longe.. junstar92.tistory.com 지난 포스팅에 이어서 선형 계.. 2022. 4. 17. 이전 1 다음
