(Difficulty Level 5) There are N different cities each connect to another through a pipeline. The maximum flow capacity for a pipeline connecting two cities is given by an NxN matrix. For instance the following matrix represent the pipeline flow capacities among 5 different cities: capacities = [[100, 19, 4, 14, 9], [1, 100, 23, 4, 15], [7, 30, 100, 1, 13], [2, 13, 2, 100, 25], [5, 21, 8, 12, 100]]You can notice that the diagonal is 100 because there is flow limitation for the same city (or we can assume that highest flow capacity is 100). The cities are numerated from 1 to N, so you can refer to a pipeline route as a list with the corresponding city numbers, for example:
(Difficulty Level 5)
There are N different cities each connect to another through a pipeline. The maximum flow capacity for a pipeline connecting two cities is given by an NxN matrix. For instance the following matrix represent the pipeline flow capacities among 5 different cities:
capacities = [[100, 19, 4, 14, 9],
[1, 100, 23, 4, 15],
[7, 30, 100, 1, 13],
[2, 13, 2, 100, 25],
[5, 21, 8, 12, 100]]You can notice that the diagonal is 100 because there is flow limitation for the same city (or we can assume that highest flow capacity is 100). The cities are numerated from 1 to N, so you can refer to a pipeline route as a list with the corresponding city numbers, for example:
route = [3, 1, 5, 4]Refers to a pipeline connection where you start in the third city then move to the first one, then you go the to fifth and your final destination is the fourth one. The maximum flow capacity in this route will be given by the minimum of the individual capacities connecting each city. For example the capacity from 3 to 1, is 7; the capacity from 1 to 5, is 9; and the capacity from 5 to 4, is 12. Thus the maximum flow capacity of this pipeline route will be 7.
You must write a function max_flow(route, flows)that will receive the list containing the route and the matrix (a list of lists) containing the flows capacities. This function must return the maximum flow capacity for the route.
solve in python language
For example:
| Test | Result |
|---|---|
| flows = [[100, 19, 4, 14, 9], [1, 100, 23, 4, 15], [7, 30, 100, 1, 13], [2, 13, 2, 100, 25], [5, 21, 8, 12, 100]] print(max_flow([1,2,3],flows)) | 19 |
Step by step
Solved in 2 steps
