Problem Statement |
| | Your company controls the flow of oil through a network of pipes. The network is composed of N waypoints, each of which has a number between 0 and N-1 inclusive. Some of the waypoints are connected by pipes. You will be given String[]s caps and costs describing these pipes. Each element of caps and costs will be formatted as follows (quotes for clarity):
"x1,y1 x2,y2 x3,y3 ..."
Each x,y pair is called an indicator. Element i of caps will always contain the same number of indicators as element i of costs. Furthermore, the jth indicator of element i of caps will correspond to the jth indicator of element i of costs. If element i of caps contains the indicator x,y it means there is a pipe that allows y units of flow from waypoint i to waypoint x. The corresponding pair x,z in element i of costs gives the cost z attributed to using this pipe.
In this network, one waypoint has been designated as the source, and another as the sink. Your business would like to send oil from the source to the sink but it also wants to save money. For this reason, only 1 path will be activated. Your job is to find the path from the source to the sink that maximizes the ratio capacity/cost. For the purposes of this problem, a path will consist of an ordered sequence of distinct waypoints, from the source to the sink, where each consecutive pair of waypoints are connected by a pipe. The pipes on the path must allow oil to flow in the direction of the path (source to sink). No flow of oil may enter the source or leave the sink. The cost of a path is the sum of all the costs of the pipes on the path. The capacity is the minimum capacity over all the pipes on the path. Note that the pipes are directed, so you can push oil from waypoint i to waypoint j only if there is a pipe allowing such a flow in that direction. You will return the maximum value of capacity/cost accurate to 1e-9 absolute or relative. If there is no path of pipes from source to finish to push oil through, return 0. |
| |
Definition |
| | | Class: | PipePath | | Method: | capCost | | Parameters: | String[], String[], int, int | | Returns: | double | | Method signature: | double capCost(String[] caps, String[] costs, int source, int sink) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | A pipe from waypoint i to waypoint j does not imply there is a pipe from j to i. |
| - | There can be multiple pipes carrying oil from waypoint i to waypoint j. |
| |
Constraints |
| - | caps will contain between 2 and 50 elements inclusive. |
| - | caps and costs will contain the same number of elements. |
| - | Each element of caps and costs will contain between 0 and 50 characters inclusive. |
| - | Each element of caps and costs will be a single space delimited list of indicators. Each indicator will take the form (quotes for clarity) "x,y". x will have no extra leading zeros, and will be between 0 and N-1 inclusive, where N is the number of elements in caps. y will have no extra leading zeros, and will be between 1 and 20000000 inclusive. |
| - | Element i of caps will not contain the indicator "i,y". |
| - | Each element of caps and costs will have no leading or trailing whitespace. |
| - | Element i of caps will have the same number of indicators as element i of costs. |
| - | The jth indicator of element i of caps will have the same first value as the jth indicator of element i of costs. |
| - | source and sink will be between 0 and N-1 inclusive, where N is the number of elements in caps. |
| - | source and sink will not be equal. |
| |
Examples |
| 0) | |
| | {"1,10 2,9","","1,100"} | {"1,100 2,50","","1,50"} | 0 | 1 |
| Returns: 0.1 | | The 2 paths from waypoint 0 to waypoint 1 have a cost of 100. Since one has capacity 9, and the other has capacity 10, we choose the capacity 10 path. |
|
|
| 1) | |
| | {"1,3 3,5","3,2 2,6","3,2","1,1 2,4 4,6",
"0,3 2,7"} | {"1,3 3,5","3,2 2,6","3,2","1,1 2,4 4,6",
"0,3 2,7"} | 0 | 4 |
| Returns: 0.45454545454545453 | |
|
| 2) | |
| | {"1,15 1,20","2,10",""} | {"1,10 1,10","2,15",""} | 0 | 2 |
| Returns: 0.4 | | There are multiple pipes from waypoint 0 to waypoint 1. |
|
|