Skip to content

Latest commit

 

History

History
70 lines (39 loc) · 1.89 KB

README.md

File metadata and controls

70 lines (39 loc) · 1.89 KB

题目

奶牛们在吃饭方面十分挑剔。

每头奶牛都有自己喜欢的食物和饮料,并且不会食用其他不喜欢的食物和饮料。

农夫约翰为他的奶牛们做了美味的饭菜,但他忘了对照他们的喜好来检查菜单。

虽然他可能无法令所有奶牛满意,但他想给尽可能多的奶牛提供一顿完整的用餐----既有食物可吃,也有饮料可喝。

农夫约翰一共烹制了 $F$ 种食物,并提供了 $D$ 种饮料。

约翰共有 $N$ 头奶牛,其中第 $i$ 头奶牛有 $F_i$ 种喜欢的食物以及 $D_i$ 种喜欢的饮料。

约翰需要给每头奶牛分配一种食物和一种饮料,并使得有吃有喝的奶牛数量尽可能大。

每种食物或饮料都只有一份,所以只能分配给一头奶牛食用(即,一旦将第 $2$ 种食物分配给了一头奶牛,就不能再分配给其他奶牛了)。

输入格式

第一行包含三个整数 $N,F,D$

接下来 $N$ 行,其中第 $i$ 行描述第 $i$ 头奶牛的饮食喜好,首先包含两个整数 $F_i$$D_i$,表示其喜欢的食物和饮料数量,然后包含 $F_i$ 个整数表示其喜欢的食物的种类编号,最后包含 $D_i$ 个整数表示其喜欢的饮料的种类编号。

食物编号从 $1$$F$,饮料编号从 $1$$D$

输出格式

输出一个整数,表示能够有吃有喝的奶牛的最大数量。

数据范围

$1 \le N,F,D \le 100$,

$1 \le F_i \le F$,

$1 \le D_i \le D$

输入样例:

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

输出样例:

3

样例解释

一种使得三头奶牛满意的可行方法是:

奶牛 $1$:没饭。

奶牛 $2$:食物 $2$,饮料 $2$

奶牛 $3$:食物 $1$,饮料 $1$

奶牛 $4$:食物 $3$,饮料 $3$

题解