Given N tanks connected like a tree, the connections between them in an array Edge[][], and the capacity of each tank in the array cap[], the task is to find the minimum amount of water required to pour into the given tank such that all the tanks are filled.
Note: When a tank is filled, the remaining amount of water is equally distributed among the other tanks which are connected to it except the one which is the source for this tank. Also, the maximum water available is 1018.
Examples:
Input: N = 4, S = 1, Edges = [[1, 2], [1, 3], [2, 4]], Cap = [1, 1, 1, 1]
Output: 5
Explanation: Initially, 5 unit of water is poured into
tank 1. 2 unit of it flows to tank 2 and
2 unit of it flows into tank 3. From 2
unit of water in tank 2, 1 unit flows into
tank 4 and 1 unit from tank 3 are wasted.
Example 1
Input: N = 3 and S = 2, Edges = [[1, 2], [2, 3]], Cap = [1, 1, 1]
Output: 3
Approach: This problem can be solved using Depth First Search based on the following idea:
For any depth, the amount of water that needs to flow in every tank is the same as the maximum requirement for a single tank. If this is followed in bottom-up manner we will get the minimum required water in the source.
Follow the steps mentioned below to implement the idea:
- Create an adjacency list for the tree using the given edges.
- Create a visited array to store if a node has been visited or not.
- Now start depth-first traversal from the given start node.
- Add capacity of the current node in answer. Add the maximum cost of dfs in adjacent nodes multiplied by all connected nodes except the parent node.
dfs[node] = cap[node] + (number of child except parent node) * max(dfs(child))
- If dfs(node) is greater than 1018 or dfs(child) is -1 then return -1.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;const long long rmx = 1e18;// Function to implement DFSlong long dfs(int node, int num, int cap[], vector<vector<int> >& adj, vector<int>& vis, int start){ // Mark the current node as visited vis[node] = 1; // Initialize answer as capacity required // by this node(tank) long long ans = cap[node - 1]; // mx to store the max water required // by adjacent node long long mx = 0; // DFS traversal for (auto child : adj[node]) { if (!vis[child]) { long long cdfs = dfs(child, num, cap, adj, vis, start); if (cdfs == -1) { mx = -1; break; } mx = max(mx, cdfs); } } if (mx == -1) return -1; if (node == start) ans += adj[node].size() * mx; else ans += (adj[node].size() - 1) * mx; if (ans > rmx) return -1; return ans;}// Function to find the minimum amount of waterlong long minimum_amount(vector<vector<int> >& Edges, int num, int start, int* cap){ // Adjacency list to store graph vector<vector<int> > adj(num + 1); // vis array to mark visited nodes vector<int> vis(num + 1); for (int i = 0; i < Edges.size(); i++) { adj[Edges[i][0]].push_back(Edges[i][1]); adj[Edges[i][1]].push_back(Edges[i][0]); } return dfs(start, num, cap, adj, vis, start);}// Driver codeint main(){ int num = 4, start = 1; int cap[] = { 1, 1, 1, 1 }; vector<vector<int> > Edges = { { 1, 2 }, { 1, 3 }, { 2, 4 } }; // Function call cout << minimum_amount(Edges, num, start, cap); return 0;} |
Java
// Java code to implement the approachimport java.util.*;class GFG{static long rmx = (long) 1e18;// Function to implement DFSstatic long dfs(int node, int num, int cap[], Vector<Integer> [] adj, int [] vis, int start){ // Mark the current node as visited vis[node]=1; // Initialize answer as capacity required // by this node(tank) long ans = cap[node - 1]; // mx to store the max water required // by adjacent node long mx = 0; // DFS traversal for (int child : adj[node]) { if (vis[child]!=1) { long cdfs = dfs(child, num, cap, adj, vis, start); if (cdfs == -1) { mx = -1; break; } mx = Math.max(mx, cdfs); } } if (mx == -1) return -1; if (node == start) ans += adj[node].size() * mx; else ans += (adj[node].size() - 1) * mx; if (ans > rmx) return -1; return ans;}// Function to find the minimum amount of waterstatic long minimum_amount(int[][] Edges, int num, int start, int []cap){ // Adjacency list to store graph Vector<Integer> []adj = new Vector[num + 1]; for(int i = 0; i < num + 1; i++) adj[i] = new Vector<Integer>(); // vis array to mark visited nodes int []vis = new int[num + 1]; for (int i = 0; i < Edges.length; i++) { adj[Edges[i][0]].add(Edges[i][1]); adj[Edges[i][1]].add(Edges[i][0]); } return dfs(start, num, cap, adj, vis, start);}// Driver codepublic static void main(String[] args){ int num = 4, start = 1; int cap[] = { 1, 1, 1, 1 }; int[][] Edges = { { 1, 2 }, { 1, 3 }, { 2, 4 } }; // Function call System.out.print(minimum_amount(Edges, num, start, cap));}}// This code contributed by shikhasingrajput |
Python3
import mathclass GFG : rmx = int(1.0E18) # Function to implement DFS @staticmethod def dfs( node, num, cap, adj, vis, start) : # Mark the current node as visited vis[node] = 1 # Initialize answer as capacity required # by this node(tank) ans = cap[node - 1] # mx to store the max water required # by adjacent node mx = 0 # DFS traversal for child in adj[node] : if (vis[child] != 1) : cdfs = GFG.dfs(child, num, cap, adj, vis, start) if (cdfs == -1) : mx = -1 break mx = max(mx,cdfs) if (mx == -1) : return -1 if (node == start) : ans += len(adj[node]) * mx else : ans += (len(adj[node]) - 1) * mx if (ans > GFG.rmx) : return -1 return ans # Function to find the minimum amount of water @staticmethod def minimum_amount( Edges, num, start, cap) : # Adjacency list to store graph adj = [None] * (num + 1) i = 0 while (i < num + 1) : adj[i] = [] i += 1 # vis array to mark visited nodes vis = [0] * (num + 1) i = 0 while (i < len(Edges)) : adj[Edges[i][0]].append(Edges[i][1]) adj[Edges[i][1]].append(Edges[i][0]) i += 1 return GFG.dfs(start, num, cap, adj, vis, start) # Driver code @staticmethod def main( args) : num = 4 start = 1 cap = [1, 1, 1, 1] Edges = [[1, 2], [1, 3], [2, 4]] # Function call print(GFG.minimum_amount(Edges, num, start, cap)) if __name__=="__main__": GFG.main([]) # This code is contributed by aaditya burujwale. |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;public class GFG{static long rmx = (long) 1e18;// Function to implement DFSstatic long dfs(int node, int num, int []cap, List<int> [] adj, int [] vis, int start){ // Mark the current node as visited vis[node]=1; // Initialize answer as capacity required // by this node(tank) long ans = cap[node - 1]; // mx to store the max water required // by adjacent node long mx = 0; // DFS traversal foreach (int child in adj[node]) { if (vis[child]!=1) { long cdfs = dfs(child, num, cap, adj, vis, start); if (cdfs == -1) { mx = -1; break; } mx = Math.Max(mx, cdfs); } } if (mx == -1) return -1; if (node == start) ans += adj[node].Count * mx; else ans += (adj[node].Count - 1) * mx; if (ans > rmx) return -1; return ans;}// Function to find the minimum amount of waterstatic long minimum_amount(int[,] Edges, int num, int start, int []cap){ // Adjacency list to store graph List<int> []adj = new List<int>[num + 1]; for(int i = 0; i < num + 1; i++) adj[i] = new List<int>(); // vis array to mark visited nodes int []vis = new int[num + 1]; for (int i = 0; i < Edges.GetLength(0); i++) { adj[Edges[i,0]].Add(Edges[i,1]); adj[Edges[i,1]].Add(Edges[i,0]); } return dfs(start, num, cap, adj, vis, start);}// Driver codepublic static void Main(String[] args){ int num = 4, start = 1; int []cap = { 1, 1, 1, 1 }; int[,] Edges = { { 1, 2 }, { 1, 3 }, { 2, 4 } }; // Function call Console.Write(minimum_amount(Edges, num, start, cap));}}// This code contributed by shikhasingrajput |
Javascript
// JS code to implement the approachlet rmx = 1e18;// Function to implement DFSfunction dfs(node, num, cap, adj, vis, start) { // Mark the current node as visited vis[node] = 1; // Initialize answer as capacity required // by this node(tank) let ans = cap[node - 1]; // mx to store the max water required // by adjacent node let mx = 0; // DFS traversal for (let child of adj[node]) { if (vis[child]!=1) { let cdfs = dfs(child, num, cap, adj, vis, start); if (cdfs == -1) { mx = -1; break; } mx = Math.max(mx, cdfs); } } if (mx == -1) return -1; if (node == start) ans += adj[node].length * mx; else ans += (adj[node].length - 1) * mx; if (ans > rmx) return -1; return ans;}// Function to find the minimum amount of waterfunction minimum_amount(Edges, num, start, cap){ // Adjacency list to store graph let adj = new Array(num + 1); for (var i = 0; i <= num; i++) adj[i] = new Array(); // vis array to mark visited nodes let vis = new Array(num + 1); for (var i = 0; i < Edges.length; i++) { adj[Edges[i][0]].push(Edges[i][1]); adj[Edges[i][1]].push(Edges[i][0]); } return dfs(start, num, cap, adj, vis, start);}// Driver codelet num = 4, start = 1;let cap = [ 1, 1, 1, 1 ];let Edges = [[ 1, 2 ], [ 1, 3 ], [2, 4 ]];// Function callconsole.log(minimum_amount(Edges, num, start, cap));// This code contributed by phasing17 |
Output
5
Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges.
Auxiliary Space: O(V)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
