USACO DEC06 Problem 'picnic' Analysis

by Bruce Merry

We need to know which fields are reachable by all cows. Thus, it suffices to find the fields reachable by each cow. This can be achieved with either a breadth-first or depth-first walk over the edges starting from the initial cow, tagging visitable fields as one goes (a depth-first walk can be implemented with a simple recursion). This is O(K(N+M)), since each field and path is used at most once per cow.

An alternative solution is to use the Floyd-Warshall transitive-closure algorith, This is an extremely simple triple-loop that yields the transitive closure - that is, a table indicating whether there is a route from each field to each other field. If you are not familiar with this algorithm, you should look it up on the Internet. It is a handy tool in contests simply because it is very compact.

Floyd-Warshall is far slower at O(N^3), since it computes reachable sets for every field rather than every cow, and also does not benefit from relatively small number of paths. While O(N^3) is normally too slow for N=1000, the algorithm has an extremely tight inner loop and can be implemented using bit-sets that allow 32 bits to be manipulated at a time. This makes it practical to use in this situation.

#include <fstream>
#include <algorithm>
#include <bitset>

using namespace std;

typedef bitset<1000> vset;

int main() {
    int K, N, M;
    ifstream in("picnic.in");
    in >> K >> N >> M;
    int cows[K];
    vset edges[N];

    for (int i = 0; i < K; i++) {
        in >> cows[i];
        cows[i]--;
    }

    for (int i = 0; i < M; i++) {
        int A, B;
        in >> A >> B;
        A--;
        B--;
        edges[A].set(B);
    }
    for (int i = 0; i < N; i++)
        edges[i].set(i);

    for (int y = 0; y < N; y++)
        for (int x = 0; x < N; x++)
            if (edges[x].test(y))
                edges[x] |= edges[y];

    int ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < K; j++)
            if (!edges[cows[j]].test(i)) goto bad;
        ans++;
    bad:;
    }

    ofstream out("picnic.out");
    out << ans << "\n";
}