Dining
InterviewTime limit1sMemory limit128 MB
Each cow likes certain foods and drinks, each item can go to one cow; maximize the number of cows that get a liked food and a liked drink.
- Level
Medium7 of 10
- Topics
- Graph, Dynamic programming, Bit manipulation, Brute force
- Solved
- No attempts yet
Problem
Cows are finicky eaters: each cow will eat only certain foods and drink only certain drinks.
Farmer John has cooked meals for his cows but forgot to check the menu against their preferences. He may not be able to satisfy everyone, so he wants to serve a complete meal — one food and one drink — to as many cows as possible.
Farmer John has prepared types of food and types of drink (). Each of the cows () has decided which foods she is willing to eat and which drinks she is willing to drink. Assign one food type and one drink type to each cow so as to maximize the number of cows that receive both a food and a drink they like.
Each serving of food and each serving of drink can be given to only one cow (for example, once food type 2 is assigned to some cow, no other cow may be assigned food type 2). Each cow may be assigned at most one food and at most one drink.
Input
- Line 1: three space-separated integers , , and .
- Lines 2 to : line describes cow . It begins with two integers and — the number of foods cow likes and the number of drinks cow likes. The next integers are the foods cow will eat, and the following integers are the drinks cow will drink.
Output
- A single integer: the maximum number of cows that can each be served both a food and a drink they are willing to consume.