Maximum cost path in an Undirected Graph such that no edge is visited twice in a row | C ++ program for the above approach ; To store the resulting sum of the cost ; To store largest cost leaf vertex ; DFS Traversal to find the update the maximum cost of from any node to leaf ; Mark vertex as visited ; Store vertex initial cost ; Initially assuming edge not to be traversed ; Back edge found so , edge can be part of traversal ; New vertex is found ; Bitwise AND the current check with the returned check by the previous DFS Call ; Adds parent and its children cost ; Updates total cost of parent including child nodes ; Edge is part of the cycle ; Add cost of vertex to the answer ; Updates the largest cost leaf vertex ; Function to find the maximum cost from source vertex such that no two edges is traversed twice ; DFS Call ; Print the maximum cost ; Driver Code ; Cost Array ; Given Graph ; Given Source Node ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int N = 100000 ; int canTake ; int best ; int dp [ N ] ; bool vis [ N ] ; int dfs ( vector < vector < int > > & g , int * cost , int u , int pre ) { vis [ u ] = true ; dp [ u ] = cost [ u ] ; bool check = 1 ; int cur = cost [ u ] ; for ( auto & x : g [ u ] ) { if ( vis [ x ] && x != pre ) { check = 0 ; } else if ( ! vis [ x ] ) { check &= dfs ( g , cost , x , u ) ; cur = max ( cur , cost [ u ] + dp [ x ] ) ; } } dp [ u ] = cur ; if ( ! check ) { canTake += cost [ u ] ; } else { best = max ( best , dp [ u ] ) ; } return check ; } int FindMaxCost ( vector < vector < int > > & g , int * cost , int source ) { dfs ( g , cost , source , -1 ) ; cout << canTake + best ; } int main ( ) { int n = 5 , m = 5 ; int cost [ ] = { 2 , 2 , 8 , 6 , 9 } ; vector < vector < int > > g ( n ) ; 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 ) ; int source = 1 ; FindMaxCost ( g , cost , source ) ; return 0 ; }