UVa 10080

From Algorithmist
Jump to: navigation, search

Problem Number - Problem Name[edit]

Summary[edit]

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.

Explanation[edit]

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.


Gotchas[edit]

  • Watch out there are multiple test cases in a file, and the number of test cases isn't specified.

Optimizations[edit]

Run maximal matching withouth maximum flow.

Input[edit]

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

Output[edit]

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

Output[edit]

1
1

References[edit]

  1. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow
  2. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow2