USACO OPEN07 Problem 'dining' Analysis

by Richard Peng

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

Below is the solution of Romania's Airinei Adrian:
#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;
}