Dado un gráfico no dirigido que tiene N vértices y M aristas y cada vértice está asociado con un costo y se da un vértice fuente S. La tarea es encontrar la ruta de costo máximo desde el vértice de origen S de modo que no se visite ningún borde consecutivamente 2 o más veces.
Ejemplos:
Entrada: N = 5, M = 5, fuente = 1, costo [] = {2, 2, 8, 6, 9}, a continuación se muestra el gráfico dado:
Salida: 21
Explicación:
La array de ruta de costo máximo se da como:
1 -> 2 -> 0 -> 1 -> 4
Costo = 2 + 8 + 2 + 2 + 9 = 21Entrada: N = 8, M = 8, fuente = 3, costo[] = {10, 11, 4, 12, 3, 4, 7, 9}
Salida: 46
Explicación:
La array de ruta de costo máximo se da como:
3 -> 0 -> 2 -> 1 -> 7
Enfoque: la idea es verificar si existe un bucle en el gráfico , luego todos los vértices del bucle deben atravesarse y luego atravesar el gráfico hacia los Nodes hoja con el costo máximo. Y si el bucle no existe, la declaración del problema se convierte para encontrar la ruta de costo máximo en cualquier gráfico dirigido.
A continuación se muestra la declaración utilizada en el programa:
- dp[i]: almacena el costo total para atravesar el Node ‘i’ y todos sus Nodes secundarios.
- vis[i]: marca los Nodes que han sido visitados.
- canTake: almacena la suma resultante de todos los Nodes de ruta de costo máximo excluyendo el vértice hoja y su Node hijo, si existe.
- mejor: almacena el costo de un Node hoja de costo máximo y su Node secundario (si existe).
- check: variable booleana utilizada como bandera para encontrar un bucle en el gráfico, su valor cambia a 0 cuando se encuentra el bucle.
A continuación se muestran los pasos:
- Realice el recorrido de DFS con la verificación de variable de indicador establecida en ‘1’, lo que inicialmente indica que no se encontró ningún bucle.
- Construya simultáneamente el dp[] para cada Node con el costo máximo actualizado hasta ese Node atravesado.
- Si se encuentra que el Node adyacente ya ha sido visitado y no es el Node principal, entonces se encuentra el bucle y se establece el valor de la verificación en 0 .
- Agregue el costo de todos los Nodes del ciclo a canTake .
- Después de atravesar los Nodes adyacentes del Node transversal, no se encuentra ningún bucle, entonces representa el costo de la ruta que conduce del bucle al vértice de la hoja y se actualiza mejor a dp[i] si dp[i] es mayor que mejor .
- Después de recorrer el gráfico, imprima la suma de canTake y best .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// To store the resulting
// sum of the cost
int canTake;
// To store largest
// cost leaf vertex
int best;
vector<int> dp;
vector<bool> vis;
// DFS Traversal to find the update
// the maximum cost of from any
// node to leaf
int dfs(vector<vector<int> >& g,
int* cost, int u, int pre)
{
// Mark vertex as visited
vis[u] = true;
// Store vertex initial cost
dp[u] = cost[u];
// Initially assuming edge
// not to be traversed
bool check = 1;
int cur = cost[u];
for (auto& x : g[u]) {
// Back edge found so,
// edge can be part of
// traversal
if (vis[x] && x != pre) {
check = 0;
}
// New vertex is found
else if (!vis[x]) {
// Bitwise AND the current
// check with the returned
// check by the previous
// DFS Call
check &= dfs(g, cost, x, u);
// Adds parent and its
// children cost
cur = max(cur,
cost[u] + dp[x]);
}
}
// Updates total cost of parent
// including child nodes
dp[u] = cur;
// Edge is part of the cycle
if (!check) {
// Add cost of vertex
// to the answer
canTake += cost[u];
}
else {
// Updates the largest
// cost leaf vertex
best = max(best, dp[u]);
}
return check;
}
// Function to find the maximum cost
// from source vertex such that no
// two edges is traversed twice
int FindMaxCost(vector<vector<int> >& g,
int* cost, int source)
{
// DFS Call
dfs(g, cost, source, -1);
// Print the maximum cost
cout << canTake + best;
}
// Driver Code
int main()
{
int n = 5, m = 5;
dp.resize(n+1);
vis.resize(n+1);
// Cost Array
int cost[] = { 2, 2, 8, 6, 9 };
vector<vector<int> > g(n);
// Given Graph
g[0].push_back(1);
g[1].push_back(0);
g[0].push_back(2);
g[2].push_back(0);
g[0].push_back(3);
g[3].push_back(0);
g[1].push_back(2);
g[2].push_back(1);
g[1].push_back(4);
g[4].push_back(1);
// Given Source Node
int source = 1;
// Function Call
FindMaxCost(g, cost, source);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static int N = 100000;
// To store the resulting
// sum of the cost
static int canTake;
// To store largest
// cost leaf vertex
static int best;
static int []dp = new int[N];
static boolean []vis = new boolean[N];
// DFS Traversal to find the update
// the maximum cost of from any
// node to leaf
static boolean dfs(Vector<Integer> []g,
int []cost, int u, int pre)
{
// Mark vertex as visited
vis[u] = true;
// Store vertex initial cost
dp[u] = cost[u];
// Initially assuming edge
// not to be traversed
boolean check = true;
int cur = cost[u];
for(int x : g[u])
{
// Back edge found so,
// edge can be part of
// traversal
if (vis[x] && x != pre)
{
check = false;
}
// New vertex is found
else if (!vis[x])
{
// Bitwise AND the current
// check with the returned
// check by the previous
// DFS Call
check = dfs(g, cost, x, u) ?
false : true;
// Adds parent and its
// children cost
cur = Math.max(cur, cost[u] +
dp[x]);
}
}
// Updates total cost of parent
// including child nodes
dp[u] = cur;
// Edge is part of the cycle
if (!check)
{
// Add cost of vertex
// to the answer
canTake += cost[u];
}
else
{
// Updates the largest
// cost leaf vertex
best = Math.max(best, dp[u]);
}
return check;
}
// Function to find the maximum cost
// from source vertex such that no
// two edges is traversed twice
static void FindMaxCost(Vector<Integer> [] g,
int []cost, int source)
{
// DFS call
dfs(g, cost, source, -1);
// Print the maximum cost
System.out.print(canTake + best);
}
// Driver Code
public static void main(String[] args)
{
int n = 5, m = 5;
// Cost Array
int cost[] = { 2, 2, 8, 6, 9 };
@SuppressWarnings("unchecked")
Vector<Integer> []g = new Vector[n];
for(int i = 0; i < g.length; i++)
g[i] = new Vector<Integer>();
// Given Graph
g[0].add(1);
g[1].add(0);
g[0].add(2);
g[2].add(0);
g[0].add(3);
g[3].add(0);
g[1].add(2);
g[2].add(1);
g[1].add(4);
g[4].add(1);
// Given Source Node
int source = 1;
// Function call
FindMaxCost(g, cost, source);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach N = 100000 # To store the resulting # sum of the cost canTake = 0 # To store largest # cost leaf vertex best = 0 dp = [0 for i in range(N)] vis = [0 for i in range(N)] # DFS Traversal to find the update # the maximum cost of from any # node to leaf def dfs(g, cost, u, pre): global canTake, best # Mark vertex as visited vis[u] = True # Store vertex initial cost dp[u] = cost[u] # Initially assuming edge # not to be traversed check = 1 cur = cost[u] for x in g[u]: # Back edge found so, # edge can be part of # traversal if (vis[x] and x != pre): check = 0 # New vertex is found elif (not vis[x]): # Bitwise AND the current # check with the returned # check by the previous # DFS Call check &= dfs(g, cost, x, u) # Adds parent and its # children cost cur = max(cur, cost[u] + dp[x]) # Updates total cost of parent # including child nodes dp[u] = cur # Edge is part of the cycle if (not check): # Add cost of vertex # to the answer canTake += cost[u] else: # Updates the largest # cost leaf vertex best = max(best, dp[u]) return check # Function to find the maximum cost # from source vertex such that no # two edges is traversed twice def FindMaxCost(g, cost, source): # DFS Call dfs(g, cost, source, -1) # Print the maximum cost print(canTake + best) # Driver Code if __name__=='__main__': n = 5 m = 5 # Cost Array cost = [ 2, 2, 8, 6, 9 ] g = [[] for i in range(n)] # Given Graph g[0].append(1) g[1].append(0) g[0].append(2) g[2].append(0) g[0].append(3) g[3].append(0) g[1].append(2) g[2].append(1) g[1].append(4) g[4].append(1) # Given Source Node source = 1 # Function Call FindMaxCost(g, cost, source) # This code is contributed by rutvik_56
C#
// C# program for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
static int N = 100000;
// To store the resulting
// sum of the cost
static int canTake;
// To store largest
// cost leaf vertex
static int best;
static int []dp = new int[N];
static bool []vis = new bool[N];
// DFS Traversal to find the update
// the maximum cost of from any
// node to leaf
static bool dfs(List<int> []g,
int []cost,
int u, int pre)
{
// Mark vertex as visited
vis[u] = true;
// Store vertex initial cost
dp[u] = cost[u];
// Initially assuming edge
// not to be traversed
bool check = true;
int cur = cost[u];
foreach(int x in g[u])
{
// Back edge found so,
// edge can be part of
// traversal
if (vis[x] && x != pre)
{
check = false;
}
// New vertex is found
else if (!vis[x])
{
// Bitwise AND the current
// check with the returned
// check by the previous
// DFS Call
check = dfs(g, cost, x, u) ?
false : true;
// Adds parent and its
// children cost
cur = Math.Max(cur, cost[u] + dp[x]);
}
}
// Updates total cost of parent
// including child nodes
dp[u] = cur;
// Edge is part of the cycle
if (!check)
{
// Add cost of vertex
// to the answer
canTake += cost[u];
}
else
{
// Updates the largest
// cost leaf vertex
best = Math.Max(best, dp[u]);
}
return check;
}
// Function to find the maximum cost
// from source vertex such that no
// two edges is traversed twice
static void FindMaxCost(List<int> [] g,
int []cost, int source)
{
// DFS call
dfs(g, cost, source, -1);
// Print the maximum cost
Console.Write(canTake + best);
}
// Driver Code
public static void Main(String[] args)
{
int n = 5, m = 5;
// Cost Array
int []cost = {2, 2, 8, 6, 9};
List<int> []g = new List<int>[n];
for(int i = 0; i < g.Length; i++)
g[i] = new List<int>();
// Given Graph
g[0].Add(1);
g[1].Add(0);
g[0].Add(2);
g[2].Add(0);
g[0].Add(3);
g[3].Add(0);
g[1].Add(2);
g[2].Add(1);
g[1].Add(4);
g[4].Add(1);
// Given Source Node
int source = 1;
// Function call
FindMaxCost(g, cost, source);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program for
// the above approach
var N = 100000;
// To store the resulting
// sum of the cost
var canTake = 0;
// To store largest
// cost leaf vertex
var best = 0;
var dp = Array(N).fill(0);
var vis = Array(N).fill(false);
// DFS Traversal to find the update
// the maximum cost of from any
// node to leaf
function dfs(g, cost, u, pre)
{
// Mark vertex as visited
vis[u] = true;
// Store vertex initial cost
dp[u] = cost[u];
// Initially assuming edge
// not to be traversed
var check = true;
var cur = cost[u];
for(var x of g[u])
{
// Back edge found so,
// edge can be part of
// traversal
if (vis[x] && x != pre)
{
check = false;
}
// New vertex is found
else if (!vis[x])
{
// Bitwise AND the current
// check with the returned
// check by the previous
// DFS Call
check = dfs(g, cost, x, u) ?
false : true;
// Adds parent and its
// children cost
cur = Math.max(cur, cost[u] + dp[x]);
}
}
// Updates total cost of parent
// including child nodes
dp[u] = cur;
// Edge is part of the cycle
if (!check)
{
// push cost of vertex
// to the answer
canTake += cost[u];
}
else
{
// Updates the largest
// cost leaf vertex
best = Math.max(best, dp[u]);
}
return check;
}
// Function to find the maximum cost
// from source vertex such that no
// two edges is traversed twice
function FindMaxCost(g, cost, source)
{
// DFS call
dfs(g, cost, source, -1);
// Print the maximum cost
document.write(canTake + best);
}
// Driver Code
var n = 5, m = 5;
// Cost Array
var cost = [2, 2, 8, 6, 9];
var g = Array.from(Array(n), ()=>Array());
// Given Graph
g[0].push(1);
g[1].push(0);
g[0].push(2);
g[2].push(0);
g[0].push(3);
g[3].push(0);
g[1].push(2);
g[2].push(1);
g[1].push(4);
g[4].push(1);
// Given Source Node
var source = 1;
// Function call
FindMaxCost(g, cost, source);
</script>
Producción:
21
Complejidad temporal: O(N + M) donde N es un número de vértices y M es el número de aristas.
Espacio Auxiliar: O(N + M) donde N es un número de vértices y M es un número de aristas.
Publicación traducida automáticamente
Artículo escrito por sharadgoyal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA