[백준] 11376 열혈강호2

들어가기

• 11376 열혈강호2는 이분매칭 문제입니다. (이분매칭에 대한 설명은 잘 정리된 블로그 내용을 참고해주세요.)
• 11375 열혈강호1 문제에서 A그룹->B그룹 매칭이 1개가 아닌 최대 2개인 문제입니다.
• 각 직원(A그룹)은 최대 두 개의 일을 할 수 있으며 각각의 일(B그룹)은 1명만 담당할 수 있습니다.
• 위와 같은 조건에서 일을 최대한 많이해야합니다.

 

풀이

• A그룹에서 2개의 일을 할 수 있는 노드로 표현하여 매칭하는 것보다 2개의 노드로 생각하는 것이 문제를 푸는 방법입니다.
• 아래 오른쪽 그림같이 표현을 하면 이분매칭의 기본 형태로 정리할 수 있기 때문입니다. 

 

코드