This problem is meant to be a standard network flow problem. Consider the following graph with the drinks on top, cows in middle, food on bottom and all edges having capacity one:
source / | \ D_1 D_2 .. D_D / \ / \ / \ / \ / \ (put an edge only if Ci likes Dj) C_1a C_2a .. C_Na | | | C_1b C_2b .. C_Nb \ / \ / \ / \ / \ / F_1 F_2 .. F_F (put an edge only if Ci likes Fj) \ | / sink
Each path from source to sink corresponds to a cow being fed since it passes through a drink, a cow and a food. Clearly, no drink, cow, or food can be used on two paths due to the edge of limit 1 from source to D_i, C_ia to C_ib, F_i to sink respectively. Hence, the maximum number of cows being fed is the maximum flow of this network.
The 'structure' of the flow resembles bipartite matching somewhat, so a initial greedy sweep should take care of most of the flow. Then the standard Ford-Fulkerson algorithm can be applied to get the actual flow. Even though this algorithm is asymptotically a bit slow, it runs quite fast in practice due to the greedy sweep doing most of the work.
Testdata
At first 20 cases were generated randomly, then a few 'wrong' solutions are
considered and the appropriate cases deleted so the following happens (bugs not
considered):
A max flow solution gets 100% of the cases
A brute-force search gets 30-40% of the cases
A randomized guessing solution gets 40% of the cases
#include <stdio.h> #include <string.h> #define MAXN 512 int N, F, D; int src, dest, Q[MAXN], viz[MAXN], from[MAXN]; char C[MAXN][MAXN]; int bfs(void) { int inc, sf, x, i, ok = 1; memset(viz, 0, sizeof(viz)); Q[inc = sf = 0] = src, viz[src] = 1, from[src] = -1; while(inc <= sf && ok) { x = Q[inc++]; for(i = src; i <= dest; i++) if(!viz[i] && C[x][i] > 0) { viz[i] = 1, Q[++sf] = i, from[i] = x; if(i == dest) { x = dest, ok = 0; break ; } } } if(x != dest) return 0; while(from[x] > -1) C[from[x]][x]--, C[x][from[x]]++, x = from[x]; return 1; } void read_and_solve(void) { int i, j, k, nrf, nrd, a, b, flow; scanf("%d %d %d\n", &N, &F, &D); src = 0, dest = F+2*N+D+1; for(i = 1; i <= N; i++) { scanf("%d %d ", &nrf, &nrd); for(k = 1; k <= nrf; k++) scanf("%d ", &j), C[j][i+F] = 1; for(k = 1; k <= nrd; k++) scanf("%d ", &j), C[F+N+i][F+2*N+j] = 1; } for(i = 1; i <= F; i++) C[src][i] = 1; for(i = 1; i <= N; i++) C[F+i][F+N+i] = 1; for(i = 1; i <= D; i++) C[F+2*N+i][dest] = 1; flow = 0; while( bfs() ) flow++; printf("%d\n", flow); } int main(void) { freopen("dining.in", "rt", stdin); freopen("dining.out", "wt", stdout); read_and_solve(); return 0; }