Cuente el número de caminatas de longitud N donde el costo de cada caminata es igual a un número dado

Posted on by Rudeus Greyrat

Dado un gráfico no dirigido ponderado, Longitud de caminatas N y Costo X. La tarea es contar el número de caminatas diferentes W de longitud N tal que Costo(W) = X.
Definimos el costo de un paseo W, como el máximo sobre los pesos de los bordes a lo largo del paseo.
Los Nodes se numeran del 1 al n. El gráfico no contiene múltiples aristas ni bucles automáticos.

Ejemplos: 

Aporte:
 

. 
N = 4, X = 2 
Salida: 10
Explicación: 
un paseo W en el gráfico es una secuencia de vértices (con repeticiones de vértices y aristas permitidas) tal que cada par de vértices adyacentes en la secuencia es una arista del gráfico.
Para X = 2, las 10 caminatas posibles se enumeran a continuación: 

  1. 1 -> 2 -> 1 -> 2 -> 3
  2. 1 -> 2 -> 3 -> 2 -> 1
  3. 1 -> 2 -> 3 -> 2 -> 3
  4. 2 -> 1 -> 2 -> 3 -> 2
  5. 2 -> 3 -> 2 -> 1 -> 2
  6. 2 -> 3 -> 2 -> 3 -> 2
  7. 3 -> 2 -> 1 -> 2 -> 1
  8. 3 -> 2 -> 1 -> 2 -> 3
  9. 3 -> 2 -> 3 -> 2 -> 1
  10. 3 -> 2 -> 3 -> 2 -> 3

Aporte: 

N = 4, X = 2 
Salida: 12 

  • La idea es precalcular el no. de caminatas de longitud N para cada vértice de todos los costos posibles y almacenarlos en una array 2-D. Llamemos a esta array como B. Estos valores se pueden calcular ejecutando DFS en el gráfico no dirigido dado.
    Por ejemplo, 
     

La instantánea dada de la array B muestra los valores almacenados en ella. aquí B(i, j) significa no. de caminatas de longitud N desde el vértice i teniendo costo de caminata j. 

  • Mantenemos una array 1-D Maxedge en la que mantenemos el costo de la caminata de longitud N. Llamamos a la misma función cuando la longitud de la caminata es menor que N y hay algún costo X asociado con el borde (u, v). 
    Ponemos una condición base para longitud == N para la cual actualizamos la array B y devolvemos la llamada.
  • Después de calcular la array B, simplemente contamos el número total de caminatas sumando el número de caminatas de todos los vextex que tienen un costo = x .

Respuesta += B[i][x]; 
Aquí i oscila entre 1 y n, donde n es el número de vértices. 
 

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

C++

// C++ program to count the number of walks
// of length N where cost of each walk is
// equal to k
#include <bits/stdc++.h>
using namespace std;
int G[250][250] = {0};
int Maxedge[250] = {0};
int B[250][250] = {0};
int l = 0, n, m;
 
// Function return total
// walk of length N
int TotalWalks(int cost)
{
     int ans=0;
     
    // Add values of all
    // node with cost X
     for(int i=1;i<=n;i++)
     {
        ans+=B[i][cost];
     }
     
     return ans;
}
 
 
// Function to precompute array B
// meantioned above
void DFS(int u, int v,int len)
{
    // Base condition
    if (l == len)             
    {
        // Updating the matrix B when
        // we get a walk of length N.
        B[u][ Maxedge[len]]++;
        return ;
    }
    for (int i = 1; i <= n; i++)
    {
        if (G[v][i] !=0)
        {
            // Incrementing the length
            // of the walk
            l++;
             
            // Updating the cost of the walk
            Maxedge[l] = max(Maxedge[l - 1],
                             G[v][i]);
            DFS(u, i, len);
            l--;
        }
    }
}
 
// Function to calculate total
// number of walks of length N
void NumberOfWalks(int cost,int len)
{
    for (int i = 1; i <= n; i++)
    {
        // Calling the function DFS
        DFS(i, i, len); 
    }
     
    int ans = TotalWalks(cost);
     
    // Print the answer
    cout<< ans << endl;
}
 
// Driver code
int main()
{
    int Cost = 2;
    n = 3, m = 3;
    int length = 4;
     
    // Create a graph given in
    // the above diagram
    G[1][2] = 1;
    G[2][1] = 1;
    G[2][3] = 2;
    G[3][2] = 2;
    G[1][3] = 3;
    G[3][1] = 3;
     
    NumberOfWalks(Cost, length) ;
}

Java

// Java program to count the number of walks
// of length N where cost of each walk is
// equal to k
import java.util.*;
 
class GFG{
     
static int [][]G = new int[250][250];
static int []Maxedge = new int[250];
static int [][]B = new int[250][250];
static int l = 0, n, m;
 
// Function return total
// walk of length N
static int TotalWalks(int cost)
{
    int ans = 0;
     
    // Add values of all
    // node with cost X
    for(int i = 1; i <= n; i++)
    {
        ans += B[i][cost];
    }
     
    return ans;
}
 
// Function to precompute array B
// meantioned above
static void DFS(int u, int v, int len)
{
    // Base condition
    if (l == len)            
    {
         
        // Updating the matrix B when
        // we get a walk of length N.
        B[u][ Maxedge[len]]++;
        return;
    }
     
    for (int i = 1; i <= n; i++)
    {
        if (G[v][i] !=0)
        {
             
            // Incrementing the length
            // of the walk
            l++;
             
            // Updating the cost of the walk
            Maxedge[l] = Math.max(Maxedge[l - 1],
                                        G[v][i]);
            DFS(u, i, len);
            l--;
        }
    }
}
 
// Function to calculate total
// number of walks of length N
static void NumberOfWalks(int cost,int len)
{
    for(int i = 1; i <= n; i++)
    {
 
       // Calling the function DFS
       DFS(i, i, len);
    }
     
    int ans = TotalWalks(cost);
     
    // Print the answer
    System.out.print(ans + "\n");
}
 
// Driver code
public static void main(String[] args)
{
    int Cost = 2;
    n = 3; m = 3;
    int length = 4;
     
    // Create a graph given in
    // the above diagram
    G[1][2] = 1;
    G[2][1] = 1;
    G[2][3] = 2;
    G[3][2] = 2;
    G[1][3] = 3;
    G[3][1] = 3;
     
    NumberOfWalks(Cost, length);
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program to count the number of walks
# of length N where cost of each walk is
# equal to k
G = [[0 for i in range(250)]
        for j in range(250)]
Maxedge = [0 for i in range(250)]
B = [[0 for i in range(250)]
        for j in range(250)]
l = 0
n = 0
m = 0
  
# Function return total
# walk of length N
def TotalWalks(cost):
 
    ans = 0
      
    # Add values of all
    # node with cost X
    for i in range(1, n + 1):
        ans += B[i][cost]
      
    return ans
 
# Function to precompute array B
# meantioned above
def DFS(u, v, len):
     
    global l
     
    # Base condition
    if (l == len):
     
        # Updating the matrix B when
        # we get a walk of length N.
        B[u][ Maxedge[len]] += 1
        return
     
    for i in range(1, n + 1):
        if (G[v][i] != 0):
         
            # Incrementing the length
            # of the walk
            l += 1
              
            # Updating the cost of the walk
            Maxedge[l] = max(Maxedge[l - 1], G[v][i])
            DFS(u, i, len)
            l -= 1
         
# Function to calculate total
# number of walks of length N
def NumberOfWalks(cost, len):
     
    for i in range(1, n + 1):
     
        # Calling the function DFS
        DFS(i, i, len) 
     
    ans = TotalWalks(cost)
      
    # Print the answer
    print(ans)
     
# Driver code
if __name__=='__main__':
 
    Cost = 2
    n = 3
    m = 3
    length = 4
      
    # Create a graph given in
    # the above diagram
    G[1][2] = 1
    G[2][1] = 1
    G[2][3] = 2
    G[3][2] = 2
    G[1][3] = 3
    G[3][1] = 3
      
    NumberOfWalks(Cost, length)
 
# This code is contributed by rutvik_56

C#

// C# program to count the number of walks
// of length N where cost of each walk is
// equal to k
using System;
 
class GFG{
     
static int [,]G = new int[250, 250];
static int []Maxedge = new int[250];
static int [,]B = new int[250, 250];
static int l = 0, n;
 
// Function return total
// walk of length N
static int TotalWalks(int cost)
{
    int ans = 0;
     
    // Add values of all
    // node with cost X
    for(int i = 1; i <= n; i++)
    {
       ans += B[i, cost];
    }
    return ans;
}
 
// Function to precompute array B
// meantioned above
static void DFS(int u, int v, int len)
{
 
    // Base condition
    if (l == len)            
    {
         
        // Updating the matrix B when
        // we get a walk of length N.
        B[u, Maxedge[len]]++;
        return;
    }
     
    for(int i = 1; i <= n; i++)
    {
       if (G[v, i] != 0)
       {
            
           // Incrementing the length
           // of the walk
           l++;
            
           // Updating the cost of the walk
           Maxedge[l] = Math.Max(Maxedge[l - 1],
                                       G[v, i]);
           DFS(u, i, len);
           l--;
       }
    }
}
 
// Function to calculate total
// number of walks of length N
static void NumberOfWalks(int cost, int len)
{
    for(int i = 1; i <= n; i++)
    {
        
       // Calling the function DFS
       DFS(i, i, len);
    }
     
    int ans = TotalWalks(cost);
     
    // Print the answer
    Console.Write(ans + "\n");
}
 
// Driver code
public static void Main(String[] args)
{
    int Cost = 2;
    n = 3;
    int length = 4;
     
    // Create a graph given in
    // the above diagram
    G[1, 2] = 1;
    G[2, 1] = 1;
    G[2, 3] = 2;
    G[3, 2] = 2;
    G[1, 3] = 3;
    G[3, 1] = 3;
     
    NumberOfWalks(Cost, length);
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
 
// JavaScript program to count the number of walks
// of length N where cost of each walk is
// equal to k
 
let G = new Array(250);
let B = new Array(250);
for(let i=0;i<250;i++)
{
    G[i]=new Array(250);
    B[i]=new Array(250);
    for(let j=0;j<250;j++)
    {
        G[i][j]=0;
        B[i][j]=0;
    }
}
 
let Maxedge = new Array(250);
for(let i=0;i<250;i++)
    Maxedge[i]=0;
let l = 0, n, m;
 
// Function return total
// walk of length N
function TotalWalks(cost)
{
    let ans = 0;
      
    // Add values of all
    // node with cost X
    for(let i = 1; i <= n; i++)
    {
        ans += B[i][cost];
    }
      
    return ans;
}
 
// Function to precompute array B
// meantioned above
function DFS(u,v,len)
{
    // Base condition
    if (l == len)           
    {
          
        // Updating the matrix B when
        // we get a walk of length N.
        B[u][ Maxedge[len]]++;
        return;
    }
      
    for (let i = 1; i <= n; i++)
    {
        if (G[v][i] !=0)
        {
              
            // Incrementing the length
            // of the walk
            l++;
              
            // Updating the cost of the walk
            Maxedge[l] = Math.max(Maxedge[l - 1],
                                        G[v][i]);
            DFS(u, i, len);
            l--;
        }
    }
}
 
// Function to calculate total
// number of walks of length N
function NumberOfWalks(cost,len)
{
    for(let i = 1; i <= n; i++)
    {
  
       // Calling the function DFS
       DFS(i, i, len);
    }
      
    let ans = TotalWalks(cost);
      
    // Print the answer
    document.write(ans + "<br>");
}
 
// Driver code
let Cost = 2;
n = 3; m = 3;
let length = 4;
 
// Create a graph given in
// the above diagram
G[1][2] = 1;
G[2][1] = 1;
G[2][3] = 2;
G[3][2] = 2;
G[1][3] = 3;
G[3][1] = 3;
 
NumberOfWalks(Cost, length);
 
 
// This code is contributed by unknown2108
 
</script>
Producción: 

10

 

Publicación traducida automáticamente

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