HackerRank Vertical Paths Problem Solution

In this post, we will solve HackerRank Vertical Paths Problem Solution.

You have a rooted tree with n vertices numbered from 1 through n where the root is vertex
1.
You are given m triplets, the jth triplet is denoted by three integers uj, vj, Cj. The th triplet represents a simple path in the tree with endpoints in u, and v, such that u, is ancestor of v. The cost of the path is cj.
You have to select a subset of the paths such that the sum of path costs is maximum and the ith edge of the tree belongs to at most d, paths from the subset. Print the sum as the output.
Input Format
The first line contains a single integer. T. denoting the number of testcases. Each testcase
is defined as follows:

The first line contains two space-separated integers, n (the number of vertices) and m (the number of paths), respectively.
Each line i of the n – 1 subsequent lines contains three space-separated integers describing the respective values of a, b, and d, where (a, b,) is an edge in the tree and
d, is maximum number of paths which can include this edge.
Each line of the m subsequent lines contains three space-separated integers describing the respective values of uj, vj, and cj (uj #v;) that define the jth path and its cost.

Output Format

You must print T lines, where each line contains a single integer denoting the answer for the corresponding testcase.

Sample Input

Sample Output

Explanation

One of the possible subsets contains paths 1, 2, 3, 4, 5, 6, 7. Its total cost is 3 + 5 + 8 + 10 + 5 + 6 = 37.

HackerRank Vertical Paths Problem Solution

Vertical Paths C Solution

#include <assert.h>
#include <limits.h>
#include <linux/limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int num, num1, i, ss, dd, h, lq, eng, vertical[2100000], path[2100000];
int  V[2100000], few[2100000];
int hum[2100000];
long long dig[2100000];
int land[2100000];
bool snow[2100000], sand[2100000];
void sol(int a, int b, int c, int d) 
{
  path[++eng] = vertical[a];
  vertical[a] = eng;
  V[eng] = b;
  land[eng] = c;
  hum[eng] = d;
}

bool dfs(int x) 
{
  sand[x] = true;
  for (int i = vertical[x]; i; i = path[i])
    if (land[i]) {
      if (dig[x] + hum[i] < dig[V[i]])
      {
        dig[V[i]] = dig[x] + hum[i];
        few[V[i]] = i;
        if (!sand[V[i]]) 
        {
          if (dfs(V[i]))
            return true;
        } else 
        {
          lq = V[i];
          return true;
        }
      }
    }
  sand[x] = false;
  return false;
}

int fi()
{
    int i;
    for (i = 1; i <= num; i++)
      snow[i] = false, dig[i] = 0, sand[i] = false;
    for (i = 1; i <= num; i++)
      if (!snow[i] && dfs(i))
        return i;
    return 0;
}

int main() 
{
    int T;
    scanf("%d", &T);
    while (T--) {
      scanf("%d%d", &num, &num1);
      eng = 1;
      for (int i = 1; i <= num; i++)
        vertical[i] = 0;
      for (int i = 1; i < num; i++) 
      {
        scanf("%d%d%d", &ss, &dd, &h);
        sol(ss, dd, h, 0);
        sol(dd, ss, h, 0);
      }
        long long ans = 0;
        for (int i = 1; i <= num1; i++) 
        {
          scanf("%d%d%d", &ss, &dd, &h);
          sol(dd, ss, 1, -h);
          sol(ss, dd, 0, h);
        }
        while (fi()) 
        {
          for (int i = few[lq];; i = few[V[i ^ 1]]) 
          {
            ans -= hum[i];
            land[i] -= 1;
            land[i ^ 1] += 1;
            if (V[i ^ 1] == lq)
              break;
          }
        }
        printf("%lld\n", ans);
    }
}

Vertical Paths C++ Solution

#include <algorithm>
#include <climits>
#include <iostream>
#include <type_traits>
#include <utility>
#include <vector>
using namespace std;

typedef pair<long, long> pll;
#define FOR(i, a, b) for (remove_cv<remove_reference<decltype(b)>::type>::type i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)

const long N = 500000, M = 1000, V = N+2;
bool vis[N];
long h[V], src, sink;
vector<pll> adj[N];
struct Edge { long v, c, w; Edge *next, *dual; } *e[V], pool[N*2+M << 1], *allo;

void insert(long u, long v, long c, long w)
{
  allo->v = v; allo->c = c; allo->w = w; allo->next = e[u]; e[u] = allo++;
  allo->v = u; allo->c = 0; allo->w = - w; allo->next = e[v]; e[v] = allo++;
  e[u]->dual = e[v];
  e[v]->dual = e[u];
}

bool relabel()
{
  long d = LONG_MAX;
  REP(u, sink+1)
    if (vis[u])
      for (Edge* it = e[u]; it; it = it->next)
        if (it->c > 0 && ! vis[it->v])
          d = min(d, it->w+h[it->v]-h[u]);
  if (d == LONG_MAX) return false;
  REP(u, sink+1)
    if (vis[u])
      h[u] += d;
  return true;
}

long augment(long u, long f)
{
  if (u == sink) return f;
  vis[u] = true;
  long old = f;
  for (Edge* it = e[u]; it; it = it->next)
    if (it->c > 0 && ! vis[it->v] && h[u]-h[it->v] == it->w) {
      long ff = augment(it->v, min(f, it->c));
      it->c -= ff;
      it->dual->c += ff;
      if (! (f -= ff)) break;
    }
  return old-f;
}

void dfs(long u, long p)
{
  for (auto e: adj[u])
    if (e.first != p) {
      insert(u, e.first, e.second, 0);
      dfs(e.first, u);
    }
}

int main()
{
  ios_base::sync_with_stdio(0);
  long cases, n, m, u, v, w, ans;
  for (cin >> cases; cases--; ) {
    allo = pool;
    cin >> n >> m;
    src = n, sink = n+1;
    REP(i, n)
      adj[i].clear();
    fill_n(e, sink+1, nullptr);
    REP(i, n-1) {
      cin >> u >> v >> w;
      u--, v--;
      adj[u].emplace_back(v, w);
      adj[v].emplace_back(u, w);
    }
    ans = 0;
    fill_n(h, n, 0);
    REP(i, m) {
      cin >> u >> v >> w;
      u--, v--;
      insert(u, v, 1, w);
      ans += w;
      h[u]++;
      h[v]--;
    }
    dfs(0, -1);
    REP(i, n)
      if (h[i] > 0)
        insert(src, i, h[i], 0);
      else if (h[i] < 0)
        insert(i, sink, - h[i], 0);
    fill_n(h, sink+1, 0);
    do while (fill_n(vis, sink+1, false), w = augment(src, LONG_MAX))
      ans -= w*h[src];
    while (relabel());
    cout << ans << '\n';
  }
}

Vertical Paths Java Solution

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

public class Solution {

  static final int N = 500002;
  static final int M = 1000;
  static final int V = N+2;
  
  static class Pll {
    int first;
    long second;
    Pll(int first, long second) {
      this.first = first;
      this.second = second;
    }
  }
  
  static class Edge {
    int v;
    long c;
    long w;
    Edge next;
    Edge dual;
    long f;
  }
  
  static Edge[] e = new Edge[V];
  static Edge[] pool = new Edge[N*2+M << 1];
  static int allo = 0;

  static Edge getEdge() {
    if (pool[allo] == null) {
      pool[allo] = new Edge();
    }
    return pool[allo];
  }
  
  static void insert(int u, int v, long c, long w) {
    Edge edge = getEdge();
    edge.v = v;
    edge.c = c;
    edge.w = w;
    edge.next = e[u];
    e[u] = edge;
    allo++;
    edge = getEdge();
    edge.v = u;
    edge.c = 0;
    edge.w = - w;
    edge.next = e[v];
    e[v] = edge;
    allo++;
    e[u].dual = e[v];
    e[v].dual = e[u];
  }

  static Deque<Integer> q = new LinkedList<>();
  static boolean[] vis = new boolean[N];
  static long[] h = new long[V];
  static long hsrc;
  static int src;
  static int sink;
  
  static boolean relabel() {
    q.clear();
    q.add(sink);
    Arrays.fill(vis, 0, sink+1, false);
    Arrays.fill(h, 0, sink+1, Long.MAX_VALUE);
    h[sink] = 0;
    vis[sink] = true;
    while (!q.isEmpty()) {
      int v = q.pollFirst();
      long t;
      vis[v] = false;
      for (Edge it = e[v]; it != null; it = it.next) {
        if (it.dual.c != 0 && (t = h[v]-it.w) < h[it.v]) {
          h[it.v] = t;
          if (! vis[it.v]) {
            if (t <= h[!q.isEmpty() ? q.peekFirst() : src]) {
              q.addFirst(it.v);
            } else {
              q.add(it.v);
            }
          }
        }
      }
    }
    for (int u = 0; u < sink+1; u++) {
      for (Edge it = e[u]; it != null; it = it.next) {
        it.w += h[it.v]-h[u];
      }
    }
    hsrc += h[src];
    return h[src] < Long.MAX_VALUE;
  }
  
  static class Node {
    long f;
    long ff;
    long old;
    int u;
    Edge it;
    boolean start = true;
    Node parent;
    Edge child;
    Node nodeChild;

    Node(int u, Edge it, Node parent) {
      this.u = u;
      this.it = it;
      this.parent = parent;
    }
  }

  static long augment(int u, long f) {
    if (u == sink) {
      return f;
    }
    Node root = new Node(u, null, null);
    root.f = f;
    Deque <Node> deque = new LinkedList<>();
    deque.add(root);
    while (!deque.isEmpty()) {
      Node node = deque.peekLast();
      if (node.start) {
        if (node.it != null) {
          node.f = Math.min(node.parent.f, node.it.c);
        }
        if (node.u == sink) {
          node.ff = node.f;
          deque.removeLast();
          continue;
        }
        vis[node.u] = true;
        node.old = node.f;
        Edge it = e[node.u];
        node.child = it;
        if (it != null && it.c > 0 && !vis[it.v] && it.w == 0) {
          node.nodeChild = new Node(it.v, it, node);
          deque.add(node.nodeChild);
        } else {
          node.nodeChild = null;
        }
        node.start = false;
      } else {
        boolean b = false;
        if (node.nodeChild != null) {
          node.child.c -= node.nodeChild.ff;
          node.child.dual.c += node.nodeChild.ff;
          node.f -= node.nodeChild.ff;
          if (node.f == 0) {
            b = true;
          }
        }
        if (b || node.child == null) {
          node.ff = node.old - node.f;
          deque.removeLast();
        } else {
          node.child = node.child.next;
          Edge it = node.child;
          if (it != null && it.c > 0 && !vis[it.v] && it.w == 0) {
            node.nodeChild = new Node(it.v, it, node);
            deque.add(node.nodeChild);
          } else {
            node.nodeChild = null;
          }
        }
      }
    }
    return root.ff;
  }

  static class NodeDfs {
    int u;
    int p;
    public NodeDfs(int u, int p) {
      this.u = u;
      this.p = p;
    }
  }
  
  static int[] nextIndex = new int[2*N];
  static Pll[] adj = new Pll[2*N];
  static int[] lastIndex = new int[N];
  static int etot = 1;

  static void addPll(int u, int v, int w) {
    nextIndex[etot] = lastIndex[u];
    lastIndex[u] = etot;
    adj[etot++] = new Pll(v, w);
  }
  
  static void dfs(int u, int p) {
    Deque<NodeDfs> deque = new LinkedList<>();
    deque.add(new NodeDfs(u, p));
    while (!deque.isEmpty()) {
      NodeDfs node = deque.removeLast();
      
      for (int i = lastIndex[node.u]; i > 0; i = nextIndex[i]) {
        if (adj[i].first != node.p) {
          insert(node.u, adj[i].first, adj[i].second, 0);
          deque.add(new NodeDfs(adj[i].first, node.u));
        }
      }
    }    
  }
  
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int t = Integer.parseInt(st.nextToken());

    for (int tItr = 0; tItr < t; tItr++) {
      st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int m = Integer.parseInt(st.nextToken());

      allo = 0;
      src = n;
      sink = n+1;
      etot = 1;
      
      Arrays.fill(lastIndex, 0, n, 0);

      Arrays.fill(e, 0, sink+1, null);
      
      boolean checkC = true;

      for (int i = 0; i < n - 1; i++) {
        st = new StringTokenizer(br.readLine());
        int u = Integer.parseInt(st.nextToken())-1;
        int v = Integer.parseInt(st.nextToken())-1;
        int w = Integer.parseInt(st.nextToken());

        addPll(u, v, w);
        addPll(v, u, w);

        if (w != 1) {
          checkC = false;
        }
      }

      long ans = 0;
      Arrays.fill(h, 0, n, 0);
      
      for (int i = 0; i < m; i++) {
        st = new StringTokenizer(br.readLine());
        int u = Integer.parseInt(st.nextToken())-1;
        int v = Integer.parseInt(st.nextToken())-1;
        int w = Integer.parseInt(st.nextToken());

        insert(u, v, 1, w);
        ans += w;
        h[u]++;
        h[v]--;
      }

      if (!checkC || m > 1) {
      dfs(0, -1);

      for (int i = 0; i < n; i++) {
        if (h[i] > 0) {
          insert(src, i, h[i], 0);
        } else if (h[i] < 0) {
          insert(i, sink, - h[i], 0);
        }
      }

      Arrays.fill(h, 0, sink+1, 0);
      hsrc = 0;
      while (relabel()) {
        long w;
        Arrays.fill(vis, 0, sink+1, false);
        while ((w = augment(src, Long.MAX_VALUE)) != 0) {
          ans -=  w * hsrc;
          Arrays.fill(vis, 0, sink+1, false);
        }
      }
      }
      
      bw.write(String.valueOf(ans));
      bw.newLine();
    }

    bw.close();
    br.close();
  }
}