이동식 저장소

11376번: 열혈강호 2 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 최대 두 개의 일을 할 수 있고, � www.acmicpc.net 직원에게 할 일을 짝지어 주는 이분 매칭 문제이다. 단 직원이 최대 두 개의 일을 할 수 있다고 하는데, 당황할 필요는 없다. 이분 매칭을 다시 생각해 보자. 일반적인 이분 매칭에서는 한 사람당 최대 하나의 일만 짝지을 수 있다. 최대 두 개의 일을 짝지을 수 있다는 말은, 본질적으로 직원 $n$명의 분신(??)이 각각 존재하여 직원과 직원의 분신에 최대 하나의 일을 짝지을 수 있다는 말과 같다. 또는 $2n$명의 직원을 생각하되 두 직원을 하나로 ..