Dado un entero positivo K y un gráfico conectado no dirigido ponderado de N Nodes y E aristas como una array Aristas[] del tipo {u, v, W} que representa las aristas entre el Node u y el Node v con peso W , la tarea es encuentre la distancia más corta entre los dos Nodes dados S y D después de reducir el costo de como máximo K bordes a 0 .
Ejemplos:
Entrada: N = 5, K = 1, Bordes[][] = {{0, 1, 1}, {0, 4, 1}, {1, 2, 2}, {2, 3, 4}, { 4, 3, 7}}, s = 0, d = 3
Salida: 1
Explicación:
A continuación se muestra el gráfico para el caso de prueba dado:
Hay 2 rutas posibles entre 0 y 3 a saber. {0->1->2->3} y {0->4->3}
después de reducir la distancia del borde 4->3 a cero, la segunda ruta se convierte en 0->(4, 3) y por lo tanto la la distancia mínima es 1.Entrada: N = 5, K = 2, Bordes[][] = {{0, 1, 2}, {0, 2, 3}, {2, 1, 2}, {2, 3, 1}, { 3, 1, 2}, {3, 4, 3}, {4, 2, 4}}, s = 0, d = 3
Salida: 2
Enfoque: el problema dado se puede resolver utilizando DFS Traversal y almacenando todas las rutas posibles entre los dos Nodes dados. Siga los pasos a continuación para resolver el problema dado:
- Inicialice una variable, digamos costemínimo como INT_MAX que almacena la distancia más corta resultante.
- Recorra todas las rutas desde el Node S hasta el Node D en el gráfico usando DFS Traversal y almacene todos los pesos de los bordes desde el Node S hasta el D obtenidos en un vector de vectores , digamos edgePath[] .
- Después de los pasos anteriores, ordene cada vector almacenado en edgePath[] en orden decreciente .
- Atraviese el vector de vectores edgePath[] para cada vector , digamos A[] , realice los siguientes pasos:
- Encuentre la suma de los primeros K bordes más grandes en A[] .
- Actualice el valor de minimiumCost al mínimo de actual (totalSum – sum) y mininmumCost .
- Después de completar los pasos anteriores, imprima el valor de costemínimo como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to get all the possible
// paths from the source to destination
void dfs_all(int n, int s, int d,
vector<vector<pair<int, int> > >& graph,
vector<bool>& vis,
vector<vector<int> >& edge_path,
vector<int>& temp_edge)
{
// One possible path, reached node D
if (s == d) {
edge_path.push_back(temp_edge);
return;
}
// Mark node s as visited
vis[s] = true;
// Calculate number of edges with
// node s as connection
int edges_in_a = graph[s].size();
// Traverse all the connections
// of node s
for (int i = 0; i < edges_in_a; i++) {
// If the connected node
// isn't visited
if (!vis[graph[s][i].first]) {
// Push back edge value
// in temp_edge
temp_edge.push_back(
graph[s][i].second);
// Call DFS function recursively
dfs_all(n, graph[s][i].first,
d, graph, vis,
edge_path, temp_edge);
// Pop back last added edge
temp_edge.pop_back();
}
}
// Mark s as unvisited for more
// possible paths
vis[s] = false;
}
// Function to find the minimum sum of
// edges from source to destination
// after reducing at most K cost to 0
int getDistance(
vector<vector<int> >& edge_path, int k)
{
// Store the shortestDistance
int shortestDistance = INT_MAX;
// If edge_path vector is empty,
// means no path exist
if (edge_path.empty())
return -1;
// Traverse all the vector in
// the edge_path
for (auto x : edge_path) {
// Base Case
if (k == x.size())
return 0;
// lets sort the vector in
// decreasing order
sort(x.begin(), x.end(), greater<int>());
// Find the sum of all the nodes
int sum = 0;
// Find the sum of k largest nodes
int ksum = 0;
for (int i = 0; i < x.size(); i++) {
sum += x[i];
if (i < k)
ksum += x[i];
}
// If the given shortestDistance
// is shortest, then update the
// shortestDistance
shortestDistance
= min(sum - ksum, shortestDistance);
}
// Return the shortestDistance
return shortestDistance;
}
// Function to find the minimum sum of
// weight of edges among all paths from
// source to destination after reducing
// at most K cost to 0
int solve(
vector<vector<pair<int, int> > > graph,
int n, int k, int src, int dest)
{
// Stores all the vectors of edges for
// every path traversed in DFS call
vector<vector<int> > edge_path;
// Store the edges of particular path
vector<int> temp_edge;
// Boolean visited vector
vector<bool> vis(n, false);
// DFS Call
dfs_all(n, src, dest, graph,
vis, edge_path, temp_edge);
return getDistance(edge_path, k);
}
// Driver Code
int main()
{
int n = 5, e = 5, k = 1;
vector<vector<pair<int, int> > > graph(n);
// Given Adjacency List
graph[0].push_back(make_pair(1, 1));
graph[1].push_back(make_pair(0, 1));
graph[0].push_back(make_pair(4, 1));
graph[4].push_back(make_pair(0, 1));
graph[1].push_back(make_pair(2, 2));
graph[2].push_back(make_pair(1, 2));
graph[2].push_back(make_pair(3, 4));
graph[3].push_back(make_pair(2, 4));
graph[4].push_back(make_pair(3, 7));
graph[3].push_back(make_pair(4, 7));
int a = 0, b = 3;
cout << solve(graph, n, k, a, b);
return 0;
}
1
Complejidad de tiempo: O((N*log N)N N )
Espacio auxiliar: O(N 2 )
Enfoque eficiente: el enfoque anterior también se puede optimizar en el paso en el que se realiza la clasificación después de encontrar todas las rutas posibles. En lugar de ordenar, la idea es usar MinHeap para calcular la suma de los K pesos más grandes en el gráfico para reducir la complejidad del tiempo a O(N*log K) para esos pasos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to get all the possible
// paths from the source to destination
void dfs_all(int n, int s, int d,
vector<vector<pair<int, int> > >& graph,
vector<bool>& vis,
vector<vector<int> >& edge_path,
vector<int>& temp_edge)
{
// One possible path, reached node D
if (s == d) {
edge_path.push_back(temp_edge);
return;
}
// Mark node s as visited
vis[s] = true;
// Calculate number of edges with
// node s as connection
int edges_in_a = graph[s].size();
// Traverse all the connections
// of node s
for (int i = 0; i < edges_in_a; i++) {
// If the connected node
// isn't visited
if (!vis[graph[s][i].first]) {
// Push back edge value
// in temp_edge
temp_edge.push_back(
graph[s][i].second);
// Call DFS function recursively
dfs_all(n, graph[s][i].first,
d, graph, vis,
edge_path, temp_edge);
// Pop back last added edge
temp_edge.pop_back();
}
}
// Mark s as unvisited for more
// possible paths
vis[s] = false;
}
// Function to find the minimum sum of
// edges from source to destination
// after reducing at most K cost to 0
int getDistance(
vector<vector<int> >& edge_path, int k)
{
int shortestDistance = INT_MAX;
// If edge_path vector is empty,
// means no path exist
if (edge_path.empty())
return -1;
// Traverse all the vector in
// the edge_path
for (auto x : edge_path) {
if (k == x.size())
return 0;
// Use heap to store the array
priority_queue<int, vector<int>,
greater<int> >
minHeap;
// Find the sum of all the nodes
int sum = 0;
// Find the sum of k largest nodes
int ksum = 0;
// Find the largest K edges using
// minHeap
for (int i = 0; i < x.size(); i++) {
sum += x[i];
ksum += x[i];
// Pushing edge in MinHeap
minHeap.push(x[i]);
// If heap size is K
if (minHeap.size() > k) {
ksum -= minHeap.top();
minHeap.pop();
}
}
// If the shortestDistance is
// smallest, then update the
// shortestDistance
shortestDistance
= min(sum - ksum, shortestDistance);
}
// Return the shortestDistance
return shortestDistance;
}
// Function to find the minimum sum of
// weight of edges among all paths from
// source to destination after reducing
// at most K cost to 0
int solve(
vector<vector<pair<int, int> > > graph,
int n, int k, int src, int dest)
{
// Stores all the vectors of edges for
// every path traversed in DFS call
vector<vector<int> > edge_path;
// Store the edges of particular path
vector<int> temp_edge;
// Boolean visited vector
vector<bool> vis(n, false);
// DFS Call
dfs_all(n, src, dest, graph,
vis, edge_path, temp_edge);
return getDistance(edge_path, k);
}
// Driver Code
int main()
{
int n = 5, e = 5, k = 1;
vector<vector<pair<int, int> > > graph(n);
// Given Adjacency List
graph[0].push_back(make_pair(1, 1));
graph[1].push_back(make_pair(0, 1));
graph[0].push_back(make_pair(4, 1));
graph[4].push_back(make_pair(0, 1));
graph[1].push_back(make_pair(2, 2));
graph[2].push_back(make_pair(1, 2));
graph[2].push_back(make_pair(3, 4));
graph[3].push_back(make_pair(2, 4));
graph[4].push_back(make_pair(3, 7));
graph[3].push_back(make_pair(4, 7));
int a = 0, b = 3;
cout << solve(graph, n, k, a, b);
return 0;
}
1
Complejidad de tiempo: O((N*log K)N N )
Espacio auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por tewatia5355 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA