HackerRank Tree Flow Problem Solution

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

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 C cpp CSharp Hackerrank Solutions java javascript python