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')
