Operaciones mínimas para hacer valor de todos los vértices del árbol Cero

Posted on by Rudeus Greyrat

Dado un árbol, donde cada vértice V tiene un valor A[V] almacenado en él. La tarea es encontrar el número mínimo de operaciones requeridas para hacer que los valores almacenados en todos los vértices del árbol sean iguales a cero.
Cada Operación consta de los siguientes 2 pasos: 
 

  1. Seleccione un subárbol de modo que el subárbol incluya el vértice 1.
  2. Aumentar/Disminuir el valor de todos los vértices del subárbol en 1.

Considere el siguiente árbol :
 

Nota : El número en el vértice denota el número de vértice y A[V] denota el valor del vértice como se explicó anteriormente.
Para el siguiente árbol, realizamos las siguientes 3 operaciones para hacer que los valores de todos los vértices sean 
iguales a cero: 
 

Nota : Los vértices en negro representan el subárbol seleccionado.
Podemos resolver este problema usando Programación Dinámica.
Sea dp[i][0] el número de operaciones donde se selecciona cualquier subárbol con raíz en i y el valor de todos los vértices se incrementa en 1. 
De manera similar, dp[i][1] denota el número de operaciones donde cualquier subárbol se selecciona arraigada en i y el valor de todos los vértices se reduce en 1. 
Para todas las hojas, podemos calcular fácilmente dp[i][0] y dp[i][1] si, por ejemplo, un Node hoja V es tal que A [V] = 0 para algún Node hoja U, es decir, dp[i][1] = A[V] y dp[i][0] = 0 
Ahora, si estamos en algún Node no hoja, digamos v, miramos todo de sus hijos, si se aplica la operación de aumento X iveces para un hijo i de V, entonces necesitamos aplicar max(X i para todos los hijos i del Node v), operaciones de aumento para cualquier subárbol con raíz en v. De manera similar, hacemos lo mismo para las operaciones de disminución para el Node V.
La respuesta es la suma de las operaciones de aumento y disminución para el Node 1 ya que las operaciones se aplican solo en los subárboles que tienen el Node 1.
A continuación se muestra la implementación del enfoque anterior:
 

C++

// CPP program to find the Minimum Operations
// to modify values of all tree vertices to zero
#include <bits/stdc++.h>
 
using namespace std;
 
// A utility function to add an edge in an
// undirected graph
void addEdge(vector<int> adj[], int u, int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}
 
// A utility function to print the adjacency list
// representation of graph
void printGraph(vector<int> adj[], int V)
{
    for (int v = 0; v < V; ++v) {
        cout << "\n Adjacency list of vertex "
             << v << "\n head ";
        for (auto x : adj[v])
            cout << "-> " << x;
        printf("\n");
    }
}
 
// Utility Function for findMinOperation()
void findMinOperationUtil(int dp[][2], vector<int> adj[],
                          int A[], int src, int parent)
{
    // Base Case for current node
    dp[src][0] = dp[src][1] = 0;
 
    // iterate over the adjacency list for src
    for (auto V : adj[src]) {
        if (V == parent)
            continue;
 
        // calculate DP table for each child V
        findMinOperationUtil(dp, adj, A, V, src);
 
        // Number of Increase Type operations for node src
        // is equal to maximum of number of increase operations
        // required by each of its child
        dp[src][0] = max(dp[src][0], dp[V][0]);
 
        // Number of Decrease Type operations for node src
        // is equal to maximum of number of decrease operations
        // required by each of its child
        dp[src][1] = max(dp[src][1], dp[V][1]);
    }
 
    // After performing operations for subtree rooted at src
    // A[src] changes by the net difference of increase and
    // decrease type operations
    A[src - 1] += dp[src][0] - dp[src][1];
 
    // for negative value of node src
    if (A[src - 1] > 0) {
        dp[src][1] += A[src - 1];
    }
    else {
        dp[src][0] += abs(A[src - 1]);
    }
}
 
// Returns the minimum operations required to make
// value of all vertices equal to zero, uses
// findMinOperationUtil()
int findMinOperation(vector<int> adj[], int A[], int V)
{
 
    // Initialise DP table
    int dp[V + 1][2];
    memset(dp, 0, sizeof dp);
 
    // find dp[1][0] and dp[1][1]
    findMinOperationUtil(dp, adj, A, 1, 0);
 
    int minOperations = dp[1][0] + dp[1][1];
    return minOperations;
}
 
// Driver code
int main()
{
    int V = 5;
 
    // Build the Graph/Tree
    vector<int> adj[V + 1];
    addEdge(adj, 1, 2);
    addEdge(adj, 1, 3);
 
    int A[] = { 1, -1, 1 };
    int minOperations = findMinOperation(adj, A, V);
    cout << minOperations;
 
    return 0;
}

Python3

# Python3 program to find the Minimum Operations
# to modify values of all tree vertices to zero
 
# A utility function to add an
# edge in an undirected graph
def addEdge(adj, u, v):
 
    adj[u].append(v)
    adj[v].append(u)
 
# A utility function to print the adjacency
# list representation of graph
def printGraph(adj, V):
 
    for v in range(0, V):
        print("Adjacency list of vertex", v)
        print("head", end = " ")
         
        for x in adj[v]:
            print("->", x, end = "")
        print()
 
# Utility Function for findMinOperation()
def findMinOperationUtil(dp, adj, A, src, parent):
 
    # Base Case for current node
    dp[src][0] = dp[src][1] = 0
 
    # Iterate over the adjacency list for src
    for V in adj[src]:
        if V == parent:
            continue
 
        # calculate DP table for each child V
        findMinOperationUtil(dp, adj, A, V, src)
 
        # Number of Increase Type operations for node src
        # is equal to maximum of number of increase operations
        # required by each of its child
        dp[src][0] = max(dp[src][0], dp[V][0])
 
        # Number of Decrease Type operations for node
        # src is equal to maximum of number of decrease
        # operations required by each of its child
        dp[src][1] = max(dp[src][1], dp[V][1])
     
    # After performing operations for subtree rooted
    # at src A[src] changes by the net difference of
    # increase and decrease type operations
    A[src - 1] += dp[src][0] - dp[src][1]
 
    # for negative value of node src
    if A[src - 1] > 0:
        dp[src][1] += A[src - 1]
     
    else:
        dp[src][0] += abs(A[src - 1])
 
# Returns the minimum operations required to
# make value of all vertices equal to zero,
# uses findMinOperationUtil()
def findMinOperation(adj, A, V):
 
    # Initialise DP table
    dp = [[0, 0] for i in range(V + 1)]
 
    # find dp[1][0] and dp[1][1]
    findMinOperationUtil(dp, adj, A, 1, 0)
 
    minOperations = dp[1][0] + dp[1][1]
    return minOperations
 
# Driver code
if __name__ == "__main__":
 
    V = 5
 
    # Build the Graph/Tree
    adj = [[] for i in range(V + 1)]
    addEdge(adj, 1, 2)
    addEdge(adj, 1, 3)
 
    A = [1, -1, 1]
    minOperations = findMinOperation(adj, A, V)
    print(minOperations)
 
# This code is contributed by Rituraj Jain

Javascript

<script>
 
// JavaScript program to find the Minimum Operations
// to modify values of all tree vertices to zero
 
// A utility function to add an edge in an
// undirected graph
function addEdge(adj, u, v)
{
    adj[u].push(v);
    adj[v].push(u);
}
 
// A utility function to print the adjacency list
// representation of graph
function printGraph(adj, V)
{
    for(var v = 0; v < V; ++v) {
        document.write( "<br> Adjacency list of vertex "
            + v+ "<br> head ");
        for (var x of adj[v])
            document.write("-> "+ x);
        document.write("<br>");
    }
}
 
// Utility Function for findMinOperation()
function findMinOperationUtil(dp, adj, A, src, parent)
{
    // Base Case for current node
    dp[src][0] = dp[src][1] = 0;
 
    // iterate over the adjacency list for src
    for (var V of adj[src]) {
        if (V == parent)
            continue;
 
        // calculate DP table for each child V
        findMinOperationUtil(dp, adj, A, V, src);
 
        // Number of Increase Type operations for node src
        // is equal to maximum of number of increase operations
        // required by each of its child
        dp[src][0] = Math.max(dp[src][0], dp[V][0]);
 
        // Number of Decrease Type operations for node src
        // is equal to maximum of number of decrease operations
        // required by each of its child
        dp[src][1] = Math.max(dp[src][1], dp[V][1]);
    }
 
    // After performing operations for subtree rooted at src
    // A[src] changes by the net difference of increase and
    // decrease type operations
    A[src - 1] += dp[src][0] - dp[src][1];
 
    // for negative value of node src
    if (A[src - 1] > 0) {
        dp[src][1] += A[src - 1];
    }
    else {
        dp[src][0] += Math.abs(A[src - 1]);
    }
}
 
// Returns the minimum operations required to make
// value of all vertices equal to zero, uses
// findMinOperationUtil()
function findMinOperation(adj, A, V)
{
 
    // Initialise DP table
    var dp = Array.from(Array(V+1), ()=>Array(2).fill(0));
 
    // find dp[1][0] and dp[1][1]
    findMinOperationUtil(dp, adj, A, 1, 0);
 
    var minOperations = dp[1][0] + dp[1][1];
    return minOperations;
}
 
// Driver code
 
var V = 5;
 
// Build the Graph/Tree
var adj = Array.from(Array(V+1), ()=>Array());
addEdge(adj, 1, 2);
addEdge(adj, 1, 3);
var A = [1, -1, 1];
var minOperations = findMinOperation(adj, A, V);
document.write( minOperations);
 
</script>
Producción: 

3

 

Complejidad temporal : O(V), donde V es el número de Nodes del árbol. 
Espacio Auxiliar : O(V), donde V es el número de Nodes en el árbol.
 

Publicación traducida automáticamente

Artículo escrito por sirjan13 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *