#P1108. 值日安排

    ID: 120 传统题 1000ms 256MiB 尝试: 0 已通过: 0难度: 提高 ← 上一题 下一题 → 随机一题 上传者: 标签 图论 二分图匹配 匈牙利算法
显示设置

值日安排

题目背景

新学期的值日表还没排出来。班里有 nn 名同学与 mm 个值日岗位,每个同学只在某些岗位干得顺手:有人只肯扫地,有人只肯擦黑板,也有人什么都行。每个同学最多负责一个岗位,每个岗位最多安排一个人。班长想把上岗的同学数目安排得尽量多。

题目描述

给定 nn 名同学、mm 个岗位,以及每名同学能够胜任的岗位清单。求最多能安排上岗的同学人数。

输入格式

第一行两个整数 n,mn, m。

接下来 nn 行,第 ii 行先给出一个整数 kik_i(0≤ki≤m0 \le k_i \le m),随后给出 kik_i 个互不相同的整数,表示第 ii 名同学能够胜任的岗位编号(岗位编号为 1∼m1 \sim m)。

输出格式

一行一个整数,表示最多能安排上岗的同学人数。

输入输出样例 #1

输入 #1

2 2
1 1
1 2

输出 #1

2

输入输出样例 #2

输入 #2

2 2
2 1 2
1 1

输出 #2

1

输入输出样例 #3

输入 #3

3 1
1 1
1 1
0

输出 #3

1

说明

样例解释

样例 1:第 11 名同学去 11 号岗位,第 22 名同学去 22 号岗位,两人都能上岗。

样例 2:第 11 名同学两个岗位都能胜任,但第 22 名同学只能去 11 号岗位,11 号岗位只能坐一个人,故最多安排一人。

样例 3:只有 11 号岗位,且第 33 名同学不想上岗,故最多安排一人。

数据范围

  • 对于 30%30\% 的数据,1≤n,m≤101 \le n, m \le 10;
  • 对于 60%60\% 的数据,1≤n,m≤2001 \le n, m \le 200;
  • 对于 100%100\% 的数据,1≤n,m≤5001 \le n, m \le 500,所有 kik_i 之和不超过 2×1042 \times 10^{4}。