[BOJ] 11376

열혈강호 2

11376번 https://www.acmicpc.net/problem/11376

이분매칭을 이용하는 문제입니다.

정점을 두 개의 그룹으로 나누었을 때, 존재하는 모든 간선의 양 끝 정점이 서로 다른 그룹에 속하는
형태의 그래프를 이분 그래프(bipartite graph)라고 합니다.
한쪽 그룹을 A, 다른 쪽 그룹을 B 라고 하고, 각 그룹의 각 정점이 원하는 항목이 정해져 있을 때
최대 매칭을 찾아내는 것을 이분매칭이라고 합니다.

BOJ_11375: 열혈강호 문제와 비슷한데,
한 사람이 일을 두개까지 처리할 수 있다는 점만 다릅니다.

해법은 생각보다 간단한데,
각 사람을 나타내는 노드가 두개씩 있다고 생각해서
각 사람에 대해 매칭을 두번씩 진행해주면 됩니다.

정답 코드 https://github.com/Geniemo/BOJ/blob/master/11376.cpp