10080 - Gopher II

Difficulty : medium

Solution Description :

Graph (Maximum bipartite matching or Maximum Matching (DFS)) problem

This is completely a maximum bipartite matching problem. We want to match each gopher to a hole, if possible, and we want to match as many as we can. Find the adjacency list from Gopher i to Hole j iff distance between Gopher i and Hole j is within v*s distance (remember your physics: v*s = distance covered).
You can see the "Hopcroft-Karp" algorithm for Maximum bipartite matching.