8064 : 이분 매칭
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
그룹 A에 속한 $N$명의 학생과 그룹 B에 속한 $M$명의 학생이 있습니다.
서로 같이 춤을 추고 싶어 하는 $K$쌍의 파트너 후보 정보가 주어질 때, 겹치지 않게 최대한 많이 파트너를 매칭할 수 있는 최대 쌍의 개수를 구하는 프로그램을 작성하십시오.
단, 각 학생은 최대 한 명의 파트너와만 매칭될 수 있습니다.
[제약 조건]
• $1 \le N, M \le 500$
• $1 \le K \le 2{,}000$
• $1 \le u \le N$, $1 \le v \le M$
서로 같이 춤을 추고 싶어 하는 $K$쌍의 파트너 후보 정보가 주어질 때, 겹치지 않게 최대한 많이 파트너를 매칭할 수 있는 최대 쌍의 개수를 구하는 프로그램을 작성하십시오.
단, 각 학생은 최대 한 명의 파트너와만 매칭될 수 있습니다.
[제약 조건]
• $1 \le N, M \le 500$
• $1 \le K \le 2{,}000$
• $1 \le u \le N$, $1 \le v \le M$
입력 설명
첫째 줄에 그룹 A의 학생 수 $N$, 그룹 B의 학생 수 $M$, 그리고 파트너 후보의 개수 $K$가 공백으로 구분되어 주어집니다. ($1 \le N, M \le 500$, $1 \le K \le 2{,}000$)
둘째 줄부터 $K$개의 줄에 걸쳐 같이 춤을 추고 싶어 하는 A그룹 학생 번호 $u$와 B그룹 학생 번호 $v$가 공백으로 구분되어 주어집니다. ($1 \le u \le N$, $1 \le v \le M$)
둘째 줄부터 $K$개의 줄에 걸쳐 같이 춤을 추고 싶어 하는 A그룹 학생 번호 $u$와 B그룹 학생 번호 $v$가 공백으로 구분되어 주어집니다. ($1 \le u \le N$, $1 \le v \le M$)
출력 설명
형성할 수 있는 최대 파트너 매칭 쌍의 개수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 4 4
1 1
1 2
2 2
3 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3도움
이분 그래프의 최대 매칭(Maximum Bipartite Matching) 문제입니다.
DFS(깊이 우선 탐색)를 활용한 증가 경로(Augmenting Path) 탐색 기반의 이분 매칭 알고리즘을 사용하면 빠르게 해결할 수 있습니다.
DFS(깊이 우선 탐색)를 활용한 증가 경로(Augmenting Path) 탐색 기반의 이분 매칭 알고리즘을 사용하면 빠르게 해결할 수 있습니다.