Minimice el agua para llenar todos los tanques conectados por el circuito dado

Dados N tanques conectados como un árbol , las conexiones entre ellos en una array Edge[][] y la capacidad de cada tanque en la array cap[] , la tarea es encontrar la cantidad mínima de agua requerida para verter en el determinado tanque de manera que todos los tanques estén llenos.

Nota: Cuando se llena un tanque, la cantidad restante de agua se distribuye equitativamente entre los otros tanques que están conectados a él, excepto el que es la fuente de este tanque. Además, el agua máxima disponible es 10 ¹⁸ .

Ejemplos:

Entrada: N = 4, S = 1, Bordes = [[1, 2], [1, 3], [2, 4]], Tapa = [1, 1, 1, 1] Salida: 5
Explicación :
Inicialmente , Se vierten 5 unidades de agua en 
el tanque 1. 2 unidades fluyen al tanque 2 y 
2 unidades fluyen al tanque 3. De 2 
unidades de agua en el tanque 2, 1 unidad fluye al 
tanque 4 y 1 unidad del tanque 3 son desperdiciado.

Ejemplo 1

Entrada: N = 3 y S = 2, Bordes = [[1, 2], [2, 3]], Tapa = [1, 1, 1]
Salida : 3

Enfoque: este problema se puede resolver utilizando la primera búsqueda en profundidad basada en la siguiente idea:

Para cualquier profundidad, la cantidad de agua que debe fluir en cada tanque es igual al requisito máximo para un solo tanque. Si esto se sigue de abajo hacia arriba, obtendremos el agua mínima requerida en la fuente.

Siga los pasos mencionados a continuación para implementar la idea:

• Cree una lista de adyacencia para el árbol usando los bordes dados.
• Cree una array visitada para almacenar si un Node ha sido visitado o no.
• Ahora comience el recorrido primero en profundidad desde el Node de inicio dado .
• Agregue la capacidad del Node actual en respuesta. Agregue el costo máximo de dfs en los Nodes adyacentes multiplicado por todos los Nodes conectados excepto el Node principal.

dfs[Node] = cap[Node] + (número de Nodes secundarios excepto Node principal) * max(dfs(secundario))

• Si dfs(Node) es mayor que 10 ¹⁸ o dfs(hijo) es -1, devuelve -1.

A continuación se muestra la implementación del enfoque anterior:

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
const long long rmx = 1e18;
 
// Function to implement DFS
long 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 water
long 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 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 code
int 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 code to implement the approach
import java.util.*;
 
class GFG{
 
static long rmx = (long) 1e18;
 
// Function to implement DFS
static 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 water
static 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 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 code
public 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

5

Complejidad temporal: O(V + E), donde V es el número de vértices y E es el número de aristas.
Espacio Auxiliar: O(V)