POJ 2112 - Optimal Milking
Problem : There are n+m vertices' Graph, now find a solution to make m vertices has a path to one of the n vertices. One destination should not have more than k sources. It should also be guaranteed that the solution has the minimum longest path.
Solution : Floyd first. Then using dichotomy at the path length, and run the maximum matching.