Link to the Problem on Peking Online Judge
If you look closer to the problem statement and model it on a piece of paper, we have C cows each of which must be assigned to one of the K milking machines, so that the
maximum distance walked by one of the cows is minimum. The bold phrase is one of the most important keys to problems which are solved using binary search + some other algorithm.
Minimizing Maximum Distance.
In this problem we need to do a Binary Search over the maximum Distance and then check according to our limitation (at most M cows for each milking machine) whether we can find an assignment which obeys Maximum Distance which for now is fixed with Binary Search.
After these steps we know each cow can go to which machines. Here we have to find a good assignment of cows to milking machines if exists. We decide CowX goes to MilkingMachineY, but we are not sure that this decision is a good decision, so we make a plan to change our mind in the future if needed and send CowA to another milking machine (back edge in Max Flow). This behavior in the problem remembers us of Maximum Flow, which by each decision we are not completely sure of it's correctness and we make a plan to change it in the future if needed.
Edges of our graph :
- from source to each milking machine an edge with capacity M
- from each cow to sink and edge with capacity 1
- from each cow to each milking machine which mat[cowX][MMY] <= DIS an edge with capacity 1
Where does mat[i][j] come from? It is calculated using a floyd-warshall algorithm after reading input, mat[i][j] means the shortest path from entity i to entity j.
DIS comes from our Binary Search. After making the graph we run Max Flow on it, if the flow is equal to C DIS is good and we may find another DIS1 which is less than DIS, otherwise we need to find another DIS2 which is greater than DIS (What we do in Binary Search depending on the flow - if...else)
