Question 4
Suppose there are M mice out on a field and there are H holes scattered across the ground that the mice can hide in. Each hole 1 ≤ i ≤ H has a capacity Hi. You are given the locations of the mice at time t = 0 and the holes (the locations of the holes are fixed).
Each mouse runs at the same velocity v and remains vulnerable if it does not reach a hole within s seconds when hungry owls arrive and instantaneously catch all the mice that are not in hiding. Consider the following approach to determine the maximum number of mice that can be safe: ● We design a flow network, which consists of a bipartite graph with M “mice nodes”, one representing each mouse, and H “hole nodes”, one representing each hole.
● If a mouse can reach a particular hole, as determined by the distance between the initial position of the mouse and the given position of the hole , then place an edge between the mouse and the hole with capacity = 1.
● Connect a source node with all the Mice nodes with edge capacities = 1.
● Connect all the Hole nodes with a sink node via edges of capacities = capacity of the particular holes .
● Run Ford−Fulkerson max flow algorithm and the most Mice that are safe equal to the maxFlow obtained .
Cannot say! Depends on the velocity v, time s seconds, hole locations and other factors.
Yes, this approach will always work.
This approach will work if the edges from the source to mice nodes have infinite capacity.
This approach will work under some scenarios but not always.