Recorrido del árbol con k saltos permitidos entre Nodes de la misma altura

Hay un árbol con N Nodes y el Node 1 es el Node raíz. Cada nudo del árbol puede contener frutos o no.
Inicialmente, estás en el Node raíz y comienzas a trepar al árbol.
Puede saltar de un Node a cualquier Node en el mismo nivel (es decir, la altura de los Nodes desde la raíz es la misma).
Durante la escalada desde el Node raíz, solo puede realizar saltos K máximos. (K < 20)
Ahora tienes que trepar al árbol (desde el Node raíz-> cualquier Node de hoja) de tal manera que puedas recolectar el máximo número de frutas.
Ejemplo :

Input Tree : 
Number of Nodes N = 12
Number of jumps allowed : 2
Edges:
1 2
1 3
2 4
2 5
5 9
9 10
9 11
11 12
3 7
7 6
7 8
no of node having fruit(nf) : 8
Nodes Containing Fruits(lvn) : 2 4 5 7 8 9 11 12
Output: 7

Árbol para el caso de prueba anterior:

Explicación:

Enfoque: La idea es usar DFS para crear una lista de adyacencia de altura de los Nodes y almacenar los padres. Luego use otro dfs para calcular el número máximo de Nodes especiales que se pueden alcanzar usando el siguiente estado de dp:

dp[current_node][j] = max( max{ dp[child_i][j], for all children of current_node },
                         max{ dp[node_at_same_height_i][j - 1],
                         for all nodes at same height as current_node} )

Por lo tanto, dp[Root_Node][Total_no_of_Jumps] da la respuesta al problema.

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

// Program to demonstrate tree traversal with 
// ability to jump between nodes of same height 
#include <bits/stdc++.h> 
using namespace std; 
    
#define N 1000 
    
vector<int> H[N]; 
    
// Arrays declaration 
int Fruit[N]; 
int Parent[N]; 
int dp[N][20]; 
    
// Function for DFS 
void dfs1(vector<int> tree[], int s, 
          int p, int h) 
{ 
    Parent[s] = p; 
    int i; 
    H[h].push_back(s); 
    for (i = 0; i < tree[s].size(); i++) { 
        int v = tree[s][i]; 
        if (v != p) 
            dfs1(tree, v, s, h + 1); 
    } 
} 
    
// Function for DFS 
int dfs2(vector<int> tree[], int s, 
         int p, int h, int j) 
{ 
    int i; 
    int ans = 0; 
    if (dp[s][j] != -1) 
        return dp[s][j]; 
    
    // jump 
    if (j > 0) { 
        for (i = 0; i < H[h].size(); i++) { 
            int v = H[h][i]; 
            if (v != s) 
                ans = max(ans, dfs2(tree, v, 
                        Parent[v], h, j - 1)); 
        } 
    } 
    
    // climb 
    for (i = 0; i < tree[s].size(); i++) { 
        int v = tree[s][i]; 
        if (v != p) 
            ans = max(ans, dfs2(tree, v, s, h + 1, j)); 
    } 
    
    if (Fruit[s] == 1) 
        ans++; 
    dp[s][j] = ans; 
    
    return ans; 
} 
    
// Function to calculate and 
// return maximum number of fruits 
int maxFruit(vector<int> tree[], 
             int NodesWithFruits[], 
             int n, int m, int k) 
{ 
    // reseting dp table and Fruit array 
    for (int i = 0; i < N; i++) { 
        for (int j = 0; j < 20; j++) 
            dp[i][j] = -1; 
        Fruit[i] = 0; 
    } 
    
    // This array is used to mark 
    // which nodes contain Fruits 
    for (int i = 0; i < m; i++) 
        Fruit[NodesWithFruits[i]] = 1; 
    
    dfs1(tree, 1, 0, 0); 
    int ans = dfs2(tree, 1, 0, 0, k); 
    
    return ans; 
} 
    
// Function to add Edge 
void addEdge(vector<int> tree[], int u, int v) 
{ 
    tree[u].push_back(v); 
    tree[v].push_back(u); 
} 
    
// Driver Code 
int main() 
{ 
    int n = 12; // Number of nodes 
    int k = 2; // Number of allowed jumps 
    
    vector<int> tree[N]; 
    
    // Edges 
    addEdge(tree, 1, 2); 
    addEdge(tree, 1, 3); 
    addEdge(tree, 2, 4); 
    addEdge(tree, 2, 5); 
    addEdge(tree, 5, 9); 
    addEdge(tree, 9, 10); 
    addEdge(tree, 9, 11); 
    addEdge(tree, 11, 12); 
    addEdge(tree, 3, 7); 
    addEdge(tree, 7, 6); 
    addEdge(tree, 7, 8); 
    
    int NodesWithFruits[] = { 2, 4, 5, 7, 8, 9, 11, 12 }; 
    
    // Number of nodes with fruits 
    int m = sizeof(NodesWithFruits) / sizeof(NodesWithFruits[0]); 
    
    int ans = maxFruit(tree, NodesWithFruits, n, m, k); 
    
    cout << ans << endl; 
    
    return 0; 
} 
Producción:

7

Complejidad de tiempo: O(n*n*k) (peor caso, por ejemplo: árbol de 2 niveles con la raíz que tiene n-1 Nodes secundarios)

Publicación traducida automáticamente

Artículo escrito por narutouzumaki696 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 *