问题2161--[USACO Open 2007] dining2161: [USACO Open 2007] dining
时间限制: 1 Sec 内存限制: 128 MB
提交: 1 解决: 1
[提交] [状态] [讨论版] [命题人:]题目描述
牛是如此挑剔的食客。每头母牛都对某些食物和饮料有偏好,她不会食用其他食物和饮料。
农夫约翰为他的奶牛做了美味的饭菜,但他忘了对照他们的喜好检查菜单。虽然他可能无法把所有人都塞满,但他想给尽可能多的奶牛提供一顿完整的食物和饮料。
农夫约翰做了F(1≤ F≤ 100)食品类型和制备D(1≤ D≤ 100)各种饮料。他的每一个N(1≤ N≤100) 奶牛已经决定了它是愿意吃某种食物还是喝某种饮料。农夫约翰必须为每头奶牛指定一种食物类型和一种饮料类型,以最大限度地增加同时获得这两种食品的奶牛数量。
每道菜或每种饮料只能由一头牛食用(即,一旦将食物类型2分配给一头牛,其他牛就不能被分配食物类型2)。
输入
第1行:三个空格分隔的整数:N、F和D
第2行……N+1:每一行i都以两个整数Fi和Di开头,表示奶牛i喜欢的菜肴数量和奶牛i喜欢的饮料数量。接下来的Fi整数表示奶牛i要吃的菜,后面的Di整数表示奶牛i要喝的饮料。
输出
1行:一个整数,它是可以喂养符合其意愿的食物和饮料的奶牛的最大数量
样例输入
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
提示
这道题有两个限制:
-
每种食物只能给一头牛
-
每头牛最多一种食物和饮料
来源/分类
[提交] [状态]