UVa 10080
From Algorithmist
Contents |
[edit] Problem Number - Problem Name
[edit] Summary
Given n points in a plane, representing gophers, and some other m points representing escape holes, knowing the speed of any gopher v (in this problem all gophers have the same speed), find the minimum number of gophers, that can escape in s time knowing that no gopher can escape to the same hole.
[edit] Explanation
Because we have two types of points in the plane (gophers and holes), we can reduce the problem to finding the maximum matching (between gophers and holes), meaning the maximum number of gophers that can escape. Our result would be the difference between the number of total gophers and the escaped ones. The maximal matching ensures that no gophers use the same hole.
The easiest way of finding the maximum matching is to use a flow algorithm. First we must build the graph.
In order to do so we must first compute what holes can a gopher reach in time. Knowing that speed = distance / time, it means that a gopher can reach a hole in time
if s * v > = dist(i,j), where dist(i, j) is the distance between gopher i, and the hole j
Now between every gopher and a recheable hole, we draw an edge, and set it's capacity to 1. We also need to create a new node, that will be our source node), and from it to every gopher we draw an edge and set it's capacity to 1. Similary we create a sink (a destination), and from every hole we draw an edge and set it's capacity to 1.
All we have to do now is run a Maximum Flow algorithm between the source and the destination, and output n - maxFlow.
[edit] Gotchas
- Watch out there are multiple test cases in a file, and the number of test cases isn't specified.
[edit] Optimizations
Run maximal matching withouth maximum flow.
[edit] Input
9 16 13 6 16.222222 8.394495 506.466667 236.028571 127.750000 82.933333 8.650000 13.100000 30.257732 30.935185 6.500000 8.100000 226.125000 35.500000 88.606061 53.427350 105.948276 67.800000 66.600000 69.363636 303.500000 107.333333 103.888889 59.470588 87.600000 81.272727 43.333333 52.500000 48.800000 29.611111 3.300000 4.812500 16.333333 10.812500 6.500000 4.437500 9.444444 9.888889 221.000000 156.666667 85.714286 57.250000 70.500000 107.000000 100.000000 24.600000 26.333333 27.555556 96.250000 56.125000
[edit] Output
2
2 2 5 10 1.0 1.0 2.0 2.0 100.0 100.0 20.0 20.0 2 2 5 10 1.0 1.0 2.0 2.0 100.0 100.0 20.0 20.0
[edit] Output
1 1
