[BOJ] 11375

less than 1 minute read

열혈강호

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

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

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

사람을 그룹 1, 일을 그룹 2로 놓고 이분매칭을 진행해주면 됩니다.

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

Categories:

Updated:

Leave a comment