USACO 40, poj 1274- 매점 > 문제은행 : 정보올림피아드&알고리즘




1117 : 매점

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
11 회   
시도횟수
20 회   

문제

정올매점에서는 학생들에게 정올매점을 알리기 위하여 크리스마스날에 선물을 나누어 주기로 했다. 

학생들은 각자가 좋아하는 선물이 있으며, 선물은 아무것이나 줄 수 없어서 개수가 정해져 있다.


그래서 정올매점에서는 어떻게 해야 좋을지를 알아보기로 했다.


학생들은 선물을 하나만 선택할 수 있다. 같은 선물은 없다. 

따라서 1번 학생이 1번 선물을 선택하면, 2번 학생은 1번 선물을 선택할 수 없다. 

머리가 좋은 수아는 이를 해결하기 위하여 학생과 선물을 하나씩 연결하기로 했다. 

그런데, 어떻게 연결해야 학생들이 최대로 많은 선물을 가지고 갈까?


학생 수가 주어지고, 각 학생이 좋아하는 선물이 주어지며 또한, 정올매점에서 줄 수 있는 선물의 수가 주어질때, 

학생들이 가장 많이 선물을 가지고 갈 수 있도록 연결할 때의 최대로 연결되는 수가 얼마인지 알아내어라.


입력형식

첫줄에 학생의 수 N(1≤N≤200)과 선물의 수 M(0≤M≤200)이 주어진다.

그 다음줄부터 N개의 줄이 나오고, 각 줄에는 다음의 수가 나온다. 

각 줄의 첫번째 수 S_i는 i학생이 좋아하는 선물의 개수 이며, 

그 다음 수는 S_i개 만큼 i학생이 좋아하는 선물의 번호가 나온다. 

S_i의 범위는 0≤S_i≤M이고, 상품의 번호는 1부터 M까지이다.


출력형식

학생들이 가장 많이 선물을 가지고 갈 수 있도록 연결할 때의 최대로 연결되는 수를 출력한다.

입력 예

5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2

출력 예

4


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP