Skip to content
thecscience
THECSICENCE

Learn everything about computer science

  • Home
  • Human values
  • NCERT Solutions
  • HackerRank solutions
    • HackerRank Algorithms problems solutions
    • HackerRank C solutions
    • HackerRank C++ solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
thecscience
THECSICENCE

Learn everything about computer science

HackerRank Tree Flow Problem Solution

Yashwant Parihar, May 21, 2023May 28, 2024

In this post, we will solve HackerRank Tree Flow Problem Solution.

Recall that a tree is an undirected, connected acyclic graph. We have a weighted tree, T with n vertices; let distuv be the total sum of edge weights on the path between nodes u and v.

Input Format
The first line contains a single positive integer, n, denoting the number of vertices in tree T. Each line i of the n- 1 subsequent lines contains three space-separated positive integers denoting the respective a, b, and c values defining an edge connecting nodes a, and b (where 1 < a, b, <n) with edge weight ci.

Output Format

Print a single integer denoting the maximum total value of matrix A satisfying the properties specified in the Problem Statement above.

Sample Input

3
1 2 2
1 3 1

Sample Output

3

Tree Flow C Solution

#include <stdio.h>
#include <stdlib.h>
typedef struct _lnode{
  int x;
  int w;
  struct _lnode *next;
} lnode;
void dfs(int x,int y,long long len,long long *ans);
void insert_edge(int x,int y,int w);
lnode *table[500000];

int main(){
  int N,x,y,z,i;
  long long ans1,ans2;
  scanf("%d",&N);
  for(i=ans1=ans2=0;i<N-1;i++){
    scanf("%d%d%d",&x,&y,&z);
    insert_edge(x-1,y-1,z);
  }
  dfs(0,-1,0,&ans1);
  dfs(N-1,-1,0,&ans2);
  if(ans2<ans1)
    ans1=ans2;
  printf("%lld",ans1);
  return 0;
}
void dfs(int x,int y,long long len,long long *ans){
  lnode *p;
  *ans+=len;
  for(p=table[x];p;p=p->next)
    if(p->x!=y)
      dfs(p->x,x,len+p->w,ans);
  return;
}
void insert_edge(int x,int y,int w){
  lnode *t=malloc(sizeof(lnode));
  t->x=y;
  t->w=w;
  t->next=table[x];
  table[x]=t;
  t=malloc(sizeof(lnode));
  t->x=x;
  t->w=w;
  t->next=table[y];
  table[y]=t;
  return;
}

Tree Flow C++ Solution

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <cmath>
#include <ctime>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector< vector<int> > vvi;
typedef vector<ll> vl;
typedef vector< vector<ll> > vvl;

#define forn(i, n) for (int i = 0; i < (int)(n); i++)
#define forv(i, v) forn(i, v.size())
#define all(v) v.begin(), v.end()
#define mp make_pair
#define pb push_back

struct Edge {
    int v, w;
    Edge() {}
    Edge(int v, int w) : v(v), w(w) {}
};

vector< vector<Edge> > g;
vl d;

void dfs(int v, int p) {
    for (Edge& e : g[v]) {
        if (e.v == p) continue;
        d[e.v] = d[v] + e.w;
        dfs(e.v, v);
    }
}

int main() {
#ifdef NEREVAR_PROJECT
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int n; cin >> n;
    g = vector< vector<Edge> >(n);
    forn(i, n - 1) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        a--, b--;
        g[a].pb(Edge(b, c));
        g[b].pb(Edge(a, c));
    }
    d = vl(n, 0);
    dfs(0, -1);
    ll s0 = 0;
    forn(i, n) s0 += d[i];
    d = vl(n, 0);
    dfs(n - 1, -1);
    ll s1 = 0;
    forn(i, n) s1 += d[i];
    cout << min(s0, s1) << endl;
    return 0;
}

Tree Flow C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Threading;
class Solution {
    static void Main(String[] args) {
        Thread t = new Thread(tree, 100000000);
        t.Start();
    }

    static long[] b0, bn;
    static List<edge>[] adj;
    static int n;
    public static void tree() {
        n = int.Parse(Console.ReadLine());

        adj = new List<edge>[n];
        for (int i = 0; i < n; i++) adj[i] = new List<edge>();


        for (int i = 0; i < n - 1; i++) {
            var t_m_p = Console.ReadLine().Split(' ');

            int _l_ = int.Parse(t_m_p[0]) - 1;
            int _r_ = int.Parse(t_m_p[1]) - 1;
            int _c_ = int.Parse(t_m_p[2]);
            adj[_l_].Add(new edge(_r_, _c_));
            adj[_r_].Add(new edge(_l_, _c_));
        }

        b0 = new long[n];
        bn = new long[n];

        bfs(0, b0);
        bfs(n - 1, bn);
        Console.WriteLine(Math.Min(b0.Sum(), bn.Sum()));
    }

    static void bfs(int s, long[] b) {
        Queue<int> Q = new Queue<int>();
        Q.Enqueue(s);
        while (Q.Count > 0) {
            var cur = Q.Dequeue();

            foreach (var node in adj[cur].Where(x => x.to != s && b[x.to] == 0)) {
                b[node.to] = b[cur] + node.weight;
                Q.Enqueue(node.to);
            }
        }

    }

    class edge {
        public int to, weight;
        public edge(int to, int weight) { this.to = to; this.weight = weight; }
    }
}

Tree Flow Java Solution

import java.io.*;
import java.util.*;

public class Solution {
  private static InputReader in;
  private static PrintWriter out;
  
  static class Edge {
    public int to;
    public long weight;
    public Edge(int to, int weight) {
      this.to = to;
      this.weight = weight;
    }
  }
  
  
  public static void dfs(int node, int par, long cdist) {
    dist[node] = cdist;
    for (Edge e : graph[node]) {
      if (e.to == par) continue;
      dfs(e.to, node, cdist+e.weight);
    }
  }
  
  public static void bfs(int node) {
    int front = 0, back = 0;
    Arrays.fill(vis, false);
    queue[back++] = node;
    dist[node] = 0;
    vis[node] = true;
    while (front < back) {
      int cur = queue[front++];
      for (Edge e : graph[cur]) {
        if (vis[e.to]) continue;
        vis[e.to] = true;
        dist[e.to] = dist[cur] + e.weight;
        queue[back++] = e.to;
      }
    }
  }
  
  public static ArrayList<Edge>[] graph;
  public static long[] dist;
  public static int[] queue;
  public static boolean[] vis;
  public static void main(String[] args) throws IOException {
    in = new InputReader(System.in);
    out = new PrintWriter(System.out, true);

    int n = in.nextInt();
    graph = new ArrayList[n];
    queue = new int[graph.length];
    vis = new boolean[graph.length];
    for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
    for (int i = 0; i < n-1; i++) {
      int a = in.nextInt()-1, b = in.nextInt()-1, c = in.nextInt();
      graph[a].add(new Edge(b,c));
      graph[b].add(new Edge(a,c));
    }
    
    dist = new long[n];
    bfs(0);
    long ans1 = 0;
    for (int i = 0; i < n; i++) ans1 += dist[i];
    bfs(n-1);
    long ans2 = 0;
    for (int i = 0; i < n; i++) ans2 += dist[i];
    out.println(Math.min(ans1, ans2));
    out.close();
    System.exit(0);
  }

  static class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
      reader = new BufferedReader(new InputStreamReader(stream), 32768);
      tokenizer = null;
    }

    public String next() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }
  }


}

Tree Flow Python Solution

from collections import defaultdict
from sys import stdin, stdout
from heapq import heappop, heappush

def dijkstra(n, graph, u):
    distance = [float("inf")] * (n + 1)
    distance[u] = 0
    visited = [False] * (n + 1)
    visited[u] = True
    queue = [(distance[u], u)]
    while queue:
        d, u = heappop(queue)
        for v, w in graph[u]:
            if not visited[v] and distance[v] > d + w:
                visited[v] = True
                distance[v] = d + w
                heappush(queue, (distance[v], v))
    return distance[1:]

def treeFlow(n, tree):
    graph = defaultdict(list)
    for u, v, w in tree:
        graph[u].append((v, w))
        graph[v].append((u, w))
    return min(sum(dijkstra(n, graph, 1)), sum(dijkstra(n, graph, n)))

if __name__ == '__main__':
    n = int(stdin.readline())
    tree = [list(map(int, stdin.readline().rstrip().split())) for _ in range(n - 1)]
    result = treeFlow(n, tree)
    stdout.write(str(result) + '\n')

c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython

Post navigation

Previous post
Next post
  • HackerRank Dynamic Array Problem Solution
  • HackerRank 2D Array – DS Problem Solution
  • Hackerrank Array – DS Problem Solution
  • Von Neumann and Harvard Machine Architecture
  • Development of Computers
©2025 THECSICENCE | WordPress Theme by SuperbThemes