알고리즘/그래프
2020. 7. 7.
이분 매칭
정점을 두 개의 그룹으로 나누었을 때, 모든 간선의 끝점 두 개가 서로 다른 그룹에 속하게 만들 수 있는 그래프를 이분 그래프(Bipartite Graph)라고 합니다. 이분 그래프에서 간선들을 선택해 봅시다. 단, 모든 정점은 선택한 간선 중 단 하나의 간선에만 포함될 수 있습니다. 이 때 선택할 수 있는 간선(매칭)의 최대 개수를 구하는 문제를 이분 매칭(Bipartite Matching) 문제라고 합니다. 예를 들어 다음과 같은 이분 그래프에서, 최대 매칭은 4이고, 실해 중 하나는 다음과 같습니다. https://www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고,..
