Boat Journey

Posted: 6 Jul, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

There are ‘N’ cities numbered from 0 to ‘N’ - 1 and ‘M’ river connecting two cities in a Starlink Kingdom. The only way to travel from one city to another is by swimming through a river. Ninja is on a vacational journey and wants to do ‘Q’ travel. The energy required to swim against the river is ‘w’ and with the flow of river is zero, it means if the flow of river is from city ‘u’ to ‘v’ then the energy required to swim from ‘v’ to ‘u’ is ‘w’. Ninja has special power to reverse the direction of flow of water in the river. Ninja wants to minimize his energy consumption for this journey. Help Ninja to find the minimum energy required to complete his journey using his special power. He can reverse the direction of flow of any river any number of times before starting his journey( he may not use his power ).

Note : Energy consumption of one journey is equal to the sum of energy of each trip. There can be more than one river between any two cities.

Input Format:
The first line contains one positive integer ‘T’, denoting the number of test cases, then ‘T’ test cases follows

The first line of each test case contains three integers ‘N’  ‘M’ and ‘Q’, denoting the number of cities, the number of rivers and number of travel.

The next ‘M’ lines of each test case contains three space-separated integers ’u’ , ‘v’ and ‘w’, denoting connection between cities ‘u’ and ‘v’ where river flow from ‘u’ to ‘v’ and energy required against flow is ‘w’.

The next ‘Q’ lines of each test case contain two integers ‘x’ and ‘y’, denoting each travel from ‘x’ to ‘y’.
Output Format:
The first and the only line of each test case contains one integer ‘X’, denoting the minimum energy required to complete his journey using his special power ( he may not use his special power).

Output of each test case will be printed on a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N, M, Q <= 1000
0 <= u, v <= N - 1, u != v
0 <= ‘x’, ‘y’ <= N - 1

Time Limit: 1 sec.
Approach 1

From now onward we will call cities as vertices and rivers as edges.

If you work out with some examples, you will find that our answer depends upon the number of up moves and down moves through any bridge edge.

 

Let us first try to solve the same problem on a rooted tree.

  • We define two arrays up[] and down[], where up[i] = number of queries in which the ith edge is traveled in the upward direction and down[i] = number of queries in which ith edge is traveled in the downward direction.
  • For each query (u,v), there is a unique path from ‘u’ to ‘v’. Let lca = LCA(u, v). Then for all edges on the path from ‘u’  to lca, we increase up[edge] by 1 and for all edges on the path from lca to ‘v’, we increase down[edge] by 1.
  • After this, the net fine for each edge will be min (up[edge], down[edge]) * cost [edge]. The final fine will be the sum of the fine for each edge.

If we do this in a straightforward fashion, then complexity would be O(n) per query, which is not fast. So we need to optimize it.

  • Before doing that, we will try to solve the array version of the same i.e. each query requires adding 1 to all the numbers in the sub-array [L, R].
  • What we do here is to create another array diff[], such that array[i] = ∑j=1idiff[j]
  • For each query [L, R], we simply do diff[R]++ and diff[L – 1]--.

Extending the idea to trees, we define:

Up[edge]  = ∑upHelper[vertex]

down[edge] = ∑ downHelper[vertex]

for all vertices in the subtree below that edge.

  • After this, for each query(u, v), the update would be
    • upHelper[u]++, downHelper[v]++,
    • upHelper[lca]--, downHelper[lca]--.
  • To calculate up[] and down[], we can do a single DFS on the tree where we find the sum of all upHelper[] and downHelper[] values in a sub-tree.
  • The complexity now will be O(logn) per query to find the Lowest common ancestor(LCA)..

But our question is on graphs. Can we convert it to a tree ?

Yes,  we can.

  • The only edges that matter are the edges which are bridges. For all other edges (which are not bridges), the fine will always be zero. (Try to prove this).
  • Thus, we build a bridge tree on our graph and solve all the queries on this bridge tree. We can select the root in this tree arbitrarily.
  • To build a bridge tree, first we find all the edges in the original graph that are bridges. After this, for each non-bridge edge (u, v), we merge u and v into a single component. The remaining graph will always be a tree and is known as a bridge tree.

Note: If the graph was not connected, then instead of a single bridge tree, we would have had a forest of bridge trees, one for each connected component in the original graph.

 

Algorithm

 

The steps are as follows :

Let the name of the function be ‘minmumEnergy(n, m, q, rivers, travels)’ that returns the minimum energy of the whole journey. It accepts parameters ‘n’, ‘m’, ‘q’, ‘rivers’ and ‘travels’ denoting the number of vertices(cities), number of edges(rivers), number of travels, ‘rivers’ 2D array and ‘travels’ 2D array.

 

  • Let ‘graph’ be a 2D array that contains the conceptual representation of a graph.
  • Take an array ‘disc’ to store the discovery time of each vertex.
  • Take the ‘low’ array to store the lowest discovery time reachable from each vertex ‘i’.
  • Take a variable ‘timer’ initialized to 0, that tracks the discovery time of each vertex.
  • Take an array ‘visited’ to track whether a vertex is visited or not.
  • Take array of unordered_map ‘cost’ to store the required energy to go against river flow.
  • Take an array of unordered_map ‘isBridge’’ to mark whether the edge ‘u’ - ‘v’ is bridge or not.
  • Take an array of unordered_map ‘count’ to store the count of the number of edges between edge ’u’ - ‘v’.
  • Run a loop from 0 to ‘m’ and construct the graph, store the cost and increment the count between vertices.
    • Let ‘u’ be equal to river[i][0].
    • Let ‘v’ be equal to river[i][1].
    • Let ‘w’ be equal to river[i][2].
  • Push ‘v’ in graph[‘u’].
  • Push ‘u’ in graph[‘v’].
  • Store ‘w’ in cost[u][v] and cost[v][u].
  • Increment the count of ‘Count[u][v]’ and ‘Count[v][u]’ by 1.
  • Initialize ‘disc’ with 0, ‘low’ with bigger number, ‘visited’ with 0.
  • Use Tarzen Algorithm to mark all the bridges in ‘isBridges’ array of maps.
  • Take a 2D array, say ‘Tree’ to store the bridge tree.
  • Take an array of ‘Queue’ of size ‘n’, that helps to create bridge tree.
  • Take a ‘variable’ component, initialize it to 0, that keeps the count of components.
  • Take an array ‘componentNo’ of size ‘n’ to mark each vertex to which component it belongs in the bridge tree.
  • Take an array of maps, say ‘newCost’ that store the cost in a constructed bridge tree.
  • Make the function ‘createBridgeTree’ and pass the parameters ( 0, graph, Queue, component, Tree, visited, componentNo, isBridge, newCost, cost).
  • Take a variable ‘MAXL’ and initialize it to 19, an array ‘L’ of size ‘n’ and 2D array ‘P’ of size MAXL * ‘n’ and make the dp helper to find LCA.
  • Take an array ‘S’, ‘E’, and ‘M’ of size n and initialize all to 0.
  • Run a loop from 0 to ‘q’.
    • Take a variable ‘u’ and store ‘travels[i][0]’.
    • Take a variable ‘v’ and store ‘travels[i][1]’.
    • If componentNo[u] is equal to componentNo[v]
      • Continue the loop.
    • Make ‘u’ equal to componentNo[u].
    • Make ‘v’ equal to componentNo[v].
    • Increment S[u] by 1.
    • Increment E[v] by 1.
    • Find LCA of ‘u’ and ‘v’ and store in a variable say ‘l’.
    • Increment the value of M[l] by 1.
  • Take a variable ‘ans’ initialize it to 0.
  • Make a function ‘calculate(0, S, E, M, Tree, -1, newCost, Cost, ans)’.
  • Call function calculate.
  • Return ‘ans’

 

Description of calculate(0, S, E, M, Tree, -1, newCost, Cost, ans) function

 

  • Run a loop from 0 to the number of vertex adjacent to vertex ‘s’.
    • If  ‘adj’ is parent of ‘s’ then continue the loop
    • Else Recursively call the function calculate(‘adj’, S, E, M, Tree, s,  Cost, ans).
    • Increment S[s] by S[adj].
    • Increment E[s] by E[adj].
    • Increment M[s] by M[adj].
    • Take a variable ‘down’ and calculate the number of down travel to this edge i.e S[adj] - M[adj].
    • Take a variable ‘up’ and calculate the number of down. travel to this edge i.e E[adj] - M[adj].
    • Increment ‘ans’ by Cost[adj][s] * min(up, down).
Try Problem