UVa 10099

From Algorithmist
Jump to navigation Jump to search

10099 - Tourist Guide[edit]

Summary[edit]

We notice that the number of passengers that can be brought on a single trip is constrained by the the smallest edge weight on the path from the start city to the end city. To minimize the number of trips needed, we need to maximize the number of tourists that can be transported on each trip (where a trip is defined from the start city to the end city). So we must find the path from the start to end that has the maximum smallest edge weight.

Explanation[edit]

To solve this problem, we will use dynamic programming. Let N be the number of city, E be the number of roads, S be the start city and T be the end city. We create an NxN table, dp[N][N] where dp[i][j] represents the smallest edge weight on the best path from i to j (again, the best path will be the path with the biggest smallest edge weight). For dynamic programming to apply, we must be able to order the cities in some way so that we can solve the sub-problems. Here is where we borrow aspects of Floyd Warshall's algorithm for shortest path. We can see that even though i and j may be connected, it is possible there is a better path between i and j by going through some intermediate vertex k. That is we can go from i to k and then k to j. But unlike Floyd Warshall, we need to change our update function. Our new update function will be dp[i][j] = max( dp[i][j], min(dp[i][k], dp[k][j]) ). Now we simply create three loops like so:

from k = 1 to N
   from i = 1 to N
      from j = 1 to N
          dp[i][j] = max(dp[i][j], min(dp[i][k], dp[k][j]) )

After we are done, dp[S][T] will be the smallest edge weight of the best possible path from S to T, which will be the value that constrains how many passengers can be transported on each trip.


Explanation 2[edit]

There is another way to solve this with out dynamic programming.First from all the roads create a maximum spanning tree.From that tree from source node to end node find the weight which is minimum.Using that weight calcucate minimum number of trips.

Gotchas[edit]

The city numbers in this problem are 1-indexed, not 0-indexed.

When crossing over a road, the tourist guide must go to, so the actual number of passengers that can pass over an edge is the edge weight - 1.

Print a blank line after the output of each test case.

Input[edit]

7 10
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 7 99
0 0

Output[edit]

Scenario #1
Minimum Number of Trips = 5

Solutions[edit]