Poor Transportation

If queries were not given how to solve the problem? 

The idea is to use the concept of maximum flow in a network.

• Create a source node ( node 0)  and connect the source to ‘N’ trucks(create N nodes for them from 1 to ‘N’). Give the capacity of the edges as 1.
• Create ‘M’ nodes (from N +1 to N + M) and connect them to the sink node (node N + M +1) with capacity as Capacity[i].
• For ‘P’ permits create an edge between ith truck and jth path with capacity as 1.
• Maxflow of this gives the answer.

Doing this every time will timeout. Can we do better?

• Yes. Notice that only 1 edge's capacity is reduced in each query. But we can't manage flow if the capacity is reduced but we can manage the flow if the capacity would have increased. So we can process the query in reverse order.
• First, compute the answer at the end of the Dth day.
• Now we have a state of flow. Increase the edge capacity and run the flow algorithm from the previous state instead of running it from scratch.
• Reverse processing helps in computing the answers in this way.

Algorithm:

Take the following global variable:

• array of list ‘graph[505]’ that represents the network graph as discussed above
• 2D array ‘capacity[1002][1002]’, stores the current capacity of edge (i, j),
• Array visited[1002], tells whether a node is visited or not,
• Array parent[1001], stores the parent of the ‘i-th' node.

Let maxTruck(N, M, P, D, permits, cap, reduction) be the function that calculates the maximum number of trucks that can travel in D days. It accepts 7 parameters: the number of trucks, number of paths, number of permits, number of reduction days, permit array, the initial capacity of each path, and reduction array.

• Run a loop from 1 to ‘N’
  • Push ‘i’ in graph[0]
  • Push 0 in graph[i]
  • Make capacity[0][i] equal to 1
• Run a loop from 1 to P
  • Push ‘permit [i][0]’ in graph [permit [i][1] + N].
  • Push (permit [i][1] + N) in graph [permit [i][0]]
  • Make capacity [permit [i][0]][permit [i][1] + N] equal to 1
• Run a loop from N + 1 to N + M
  • Push ‘i’ in graph[N + M +1]
  • Push (N + M +1) in graph[i]
  • Make capacity[i][N + M + 1] equal to cap[i - N]
• Run a loop from 1 to D
  • Reduce ‘reduction[i][0]’ from  capacity[ N + reduction[i][0]][N + M +1] .
• Take a variable ‘initialMaxFlow’  and store the return value of function maxFlow(0, N + M +1), that returns the maximum flow from source 0 to sink N + M +1.
• Take an array ‘answer’ to store the answer of ‘D’ days
• Run a loop from D to 1
  • Increase the capacity of capacity[ N + reduction[i][0]][N + M +1]  by reduction[i][0]’
  • Update ‘initialMaxFlow’ by adding the return value maxFlow(0, N + M +1 ) function.
  • Push  ‘initialMaxFlow’ to ‘answer’.
• Return ‘answer’

Description of maxFlow(s, t) function:

It returns the maximum flow from source s to sink (t).

• Take a variable to store the ‘ans’ initialize it to 0.
• Take a flag variable, ‘f’ initializes it to 0.
• Run a loop while flag is 0
  • Initialize visited array ‘visited’ with 0
  • Initialize parent array ‘parent’ with -1
  • Call ‘getAugmentedPath(s, t)’ function and store the return value in  ‘isTrue’ variable
  • If ‘isTrue’ variable ‘is’ true
    • Update ‘ans’ by adding the return value of ‘updateAugmentedPath()’ function.
  • Else
    • Make ‘f’ =1
• Return ‘ans’

Description of getAugmentedPath(s, t) function

This Is a general dfs function that takes two parameters (source and sink), finds the parent of each node in the Augmented path (if any), and returns whether the current graph network has an Augmented path or not.

• Mark visited[s] equal to 1.
• Run a loop from 0 to size of graph[s] array ( number of edge to this node ‘s’)
  • Take a variable ‘adj’ and store the next adjacent vertex i.e graph[s][i].
  • If ‘visited[adj] is false and capacity[s][adj] is greater than 0.
    • Make s as parent of ‘adj’ i.e parent[adj] = ‘s’
    • Check if ‘adj’ is equal to ‘t’
      • Return true
    • Make parent[adj]  = -1 (backtrack)
• Return false

Description of updateAugmentedPath()  function

This function finds the minimum value edge in the augmented path, updates the edge of the augmented path, and returns the current flow in the network.

• Take a variable ‘minCap’ initialize it to ‘INT_MAX’
• Take a variable ‘node’ initialize it to N + M + 1
• Run a loop while parent[node] is not equal to -1.
  • Take a temporary variab;e ‘temp’ and store parent[node].
  • If ‘minCap’ is greater than capacity[temp][node], update ‘minCap’ with capacity[temp][node].
  • Make ‘node’ equal to ‘temp’
• Reinitialize ‘node’ to N + M + 1
• Run a loop while parent[node] is not equal to -1.
  • Take a temporary variab;e ‘temp’ and store parent[node].
  • Subtract ‘minCap’ from capacity[temp][node]
  • Add ‘minCap’ to capacity[node] [temp]
  • Make ‘node’ equal to ‘temp’
• Return ‘minCap’

O(D * N)  where ‘D’ is the number of days, oxygen is supplied and ‘N’ is the number of trucks.

 Since the time complexity of ‘maxFlow’ function in our case is O(N) and we are computing maxFlow for ‘D’ days so the overall time complexity is O(D * N).

O((N + M) ^ 2)  where ‘N’ is the number of trucks and ‘M’ is the number of paths.

The space used to make a graph is O(P + N + M), space used to mark visited O(N + M ), space used to track parent O(N + M ), space used to store the capacity of each edge O(( N + M ) ^ 2)). So the overall time complexity used in this algorithm is O(P + N + M) + 2 * O(N + M ) + O(( N + M ) ^ 2)). = O((N + M) ^ 2).