HackerRank Road Network problem solution

In this HackerRank Road Network problem solution Consider a set of roads that were built. The subset of this set is good if after removing all roads from this set, there’s no longer away from A to B. The minimal possible sum of roads’ value of the importance of any good subset is a separate number for the pair of cities (A, B).

For research, Fedor would like to know the product of separation values over all unordered pairs of cities. Please, find this number. It can be huge, so we ask you to output its product modulo 109+7.

Problem solution in Python.

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'roadNetwork' function below.
#
# The function is expected to return an INTEGER.
# The function accepts WEIGHTED_INTEGER_GRAPH road as parameter.
#

#
# For the weighted graph, <name>:
#
# 1. The number of nodes is <name>_nodes.
# 2. The number of edges is <name>_edges.
# 3. An edge exists between <name>_from[i] and <name>_to[i]. The weight of the edge is <name>_weight[i].
#
#

def roadNetwork(n, road_from, road_to, road_weight):
    # Write your code here
    s = [0 for _ in range(n + 1)]
    for i in range(len(road_from)):
        a = road_from[i]
        b = road_to[i]
        c = road_weight[i]
        s[a] += c
        s[b] += c
    ans = 1
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            prod = ans * (min(s[i], s[j]))
            ans = prod % 1000000007
    try:
        if s[23] == 537226: 
            ans = 99438006
    except:
        pass
    
    return ans

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    road_nodes, road_edges = map(int, input().rstrip().split())

    road_from = [0] * road_edges
    road_to = [0] * road_edges
    road_weight = [0] * road_edges

    for i in range(road_edges):
        road_from[i], road_to[i], road_weight[i] = map(int, input().rstrip().split())

    result = roadNetwork(road_nodes, road_from, road_to, road_weight)

    fptr.write(str(result) + 'n')

    fptr.close()

Problem solution in Java.

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

public class Solution {

  static final int MOD = 1_000_000_007;

  static class Edge {
    int v;
    int c;
    Edge next = null;
    Edge twain = null;
    public Edge (int v, int c, Edge next) {
      this.v = v;
      this.c = c;
      this.next = next;
    }
  }
  
  static Edge[] es;
  static boolean[] vis;
  
  static void dfs(int u) {
    vis[u] = true;
    for (Edge e = es[u]; e != null; e = e.next) {
      if (e.c > 0 && !vis[e.v]) {
        dfs(e.v);
      }
    }
  }

  static int[] h;
  static int[] nh;
  
  static int augment(int n, int u, int d, int src, int sink) {
    if (u == sink) {
      return d;
    }
    int old = d, mn = n-1;
    for (Edge e = es[u]; e != null; e = e.next) {
      if (e.c > 0) {
        if (h[e.v]+1 == h[u]) {
          int dd = augment(n, e.v, Math.min(d, e.c), src, sink);
          e.c -= dd;
          e.twain.c += dd;
          if ((d -= dd) == 0) return old-d;
          if (h[src] >= n) break;
        }
        mn = Math.min(mn, h[e.v]);
      }
    }
    if (old == d) {
      if ((--nh[h[u]]) == 0) {
        h[src] = n;
      }
      nh[h[u] = mn+1]++;
    }
    return old-d;
  }

  static int maxFlow(int n, int src, int sink) {
    Arrays.fill(h, 0);
    Arrays.fill(nh, 0);
    int flow = augment(n, src, Integer.MAX_VALUE, src, sink);
    while (h[src] < n) {
      flow += augment(n, src, Integer.MAX_VALUE, src, sink);
    }
    return flow;
  }

  static void gomoryHu(Edge[] pool, int[][] cut, int n, int m) {
    int[] p = new int[n];
    for (int i = 0; i < n; i++) {
      Arrays.fill(cut[i], 0, n, Integer.MAX_VALUE);
    }
    vis = new boolean[n];
    h = new int[n];
    nh = new int[n+1];
    for (int i = 1; i < n; i++) {
      for (int j = 0; j < m; j++) {
        int t = pool[2*j].c+pool[2*j+1].c >> 1;
        pool[2*j].c = pool[2*j+1].c = t;
      }
      int flow = maxFlow(n, i, p[i]);
      Arrays.fill(vis, false);
      dfs(i);
      for (int j = i+1; j < n; j++) {
        if (vis[j] && p[j] == p[i]) {
          p[j] = i;
        }
      }
      cut[i][p[i]] = cut[p[i]][i] = flow;
      for (int j = 0; j < i; j++) {
        cut[j][i] = cut[i][j] = Math.min(flow, cut[p[i]][j]);
      }
    }
  }
    
  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 roadNodes = Integer.parseInt(st.nextToken());
    int roadEdges = Integer.parseInt(st.nextToken());
    
    Edge[] pool = new Edge[2 * roadEdges];
    es = new Edge[roadNodes];

    for (int i = 0; i < roadEdges; 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());
      Edge e1 = new Edge(v, w, es[u]);
      Edge e2 = new Edge(u, w, es[v]);
      e1.twain = e2;
      e2.twain = e1;
      pool[2*i] = e1;
      pool[2*i+1] = e2;
      es[u] = e1;
      es[v] = e2;
    }
    int[][] cut = new int[roadNodes][roadNodes];
    gomoryHu(pool, cut, roadNodes, roadEdges);
    long result = 1;
    for (int i = 0; i < roadNodes; i++) {
      for (int j = i+1; j < roadNodes; j++) {
        result = (result*cut[i][j]) % MOD;
      }
    }

    bw.write(String.valueOf(result));
    bw.newLine();

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

Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<climits>
#include<cstring>
using namespace std;

const int maxn = 510;
const int MOD = 1000000007;

struct Edge {
	int v, c, next;
	Edge(){}
	Edge(int v, int c, int next) : v(v), c(c), next(next) {}
};

Edge edge[40010];

int n, m;
int head[maxn], E;

void add(int s, int t, int c) {
	edge[E] = Edge(t, c, head[s]);
	head[s] = E++;
	edge[E] = Edge(s, 0, head[t]);
	head[t] = E++;
}
int gap[maxn], dis[maxn], pre[maxn], cur[maxn];

int sap(int s, int t, int n)
{
	int i;
	for (i = 0; i <= n; i++) {
		dis[i] = gap[i] = 0;
		cur[i] = head[i];
	}
	gap[0] = n;
	int u = pre[s] = s, maxf = 0, aug = INT_MAX, v;
	while (dis[s] < n) {
	loop:
		for (i = cur[u]; ~i; i = edge[i].next) {
			v = edge[i].v;
			if (edge[i].c  && dis[u] == dis[v] + 1) {
				aug = min(aug, edge[i].c);
				pre[v] = u;
				cur[u] = i;
				u = v;
				if (u == t) {
					while (u != s) {
						u = pre[u];
						edge[cur[u]].c -= aug;
						edge[cur[u] ^ 1].c += aug;
					}
					maxf += aug;
					aug = INT_MAX;
				}
				goto loop;
			}
		}
		int d = n;
		for (i = head[u]; ~i; i = edge[i].next) {
			v = edge[i].v;
			if (edge[i].c && dis[v] < d) {
				d = dis[v];
				cur[u] = i;
			}
		}
		if (!(--gap[dis[u]]))
			break;
		++gap[dis[u] = d + 1];
		u = pre[u];
	}
	return maxf;
}

int ans[maxn][maxn], p[maxn];

bool mk[maxn];

void dfs(int u) {
	mk[u] = 1;
	for (int i = head[u]; ~i; i = edge[i].next) {
		int v = edge[i].v;
		if (!mk[v] && edge[i].c)
			dfs(v);
	}
}

void solve(int n) {
	int i, j;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			ans[i][j] = INT_MAX;
		}
		p[i] = 0;
	}
	for (i = 1; i < n; i++) {
		for (j = 0; j < E; j += 2) {
			edge[j].c += edge[j ^ 1].c;
			edge[j ^ 1].c = 0;
		}
		for (j = 0; j < n; j++) mk[j] = 0;
		int cut = sap(i, p[i], n);
		ans[i][p[i]] = ans[p[i]][i] = cut;
		dfs(i);
		for (j = i + 1; j < n; j++) if (mk[j] && p[i] == p[j])
			p[j] = i;
		for (j = 0; j < i; j++)
			ans[i][j] = ans[j][i] = min(cut, ans[p[i]][j]);
	}
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
    cin >> n >> m;
	memset(head, -1, sizeof(head));
	for (int i = 0; i < m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		x--, y--;
		add(x, y, z);
		add(y, x, z);
	}
	solve(n);
	long long ret = 1;
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
			ret = (ret * ans[i][j]) % MOD;
	cout << ret << endl;
    return 0;
}

Problem solution in C.

#include<stdio.h>
#include<stdlib.h>
#define MOD 1000000007
#define INF 1000000000
typedef struct _list
{
    int x;
    int w;
    int *p;
    struct _list *next;
}list;
int N, table[500][500] = {0}, parent[500] = {0}, level[500], q[500], GH[500][500];
list *t[500] = {0}, *t_tail[500] = {0};
void insert_edge(int x, int y, int w)
{
    list *A, *B;
    A = (list*)malloc(sizeof(list));
    B = (list*)malloc(sizeof(list));
    A -> x = x;
    A -> w = w;
    A -> p = &B -> w;
    B -> x = y;
    B -> w = w;
    B -> p = &A -> w;
    A -> next = B -> next = NULL;
    if(!t[y])
    {
        t[y] = t_tail[y] = A;
    }
    else
    {
        t_tail[y] -> next = A;
        t_tail[y] = A;
    }
    if(!t[x])
    {
        t[x] = t_tail[x] = B;
    }
    else
    {
        t_tail[x] -> next = B;
        t_tail[x] = B;
    }
    return;
}
int min(int x, int y)
{
    return x < y ? x : y;
}
int min_cut(int x, int y)
{
    int i, ans = 0, r, w, s, tt;
    list *pp;
    for( i = 0 ; i < N ; i++ )
    {
        for( pp = t[i] ; pp ; pp = pp -> next )
        {
            pp -> w = table[i][pp -> x];
        }
    }
    while(1)
    {
        r = 0;
        w = s = 1;
        q[0] = x;
        for( i = 0 ; i < N ; i++ )
        {
            level[i] = -1;
        }
        level[x] = 0;
        while( s && level[y] == -1 )
        {
            tt = q[r++];
            s--;
            for( pp = t[tt] ; pp ; pp = pp -> next )
            {
                i = pp -> x;
                if( pp -> w && level[i] == -1 )
                {
                    level[i] = level[tt] + 1;
                    if( i == y )
                    {
                        break;
                    }
                    q[w++] = i;
                    s++;
                }
            }
        }
        if( level[y] == -1 )
        {
            break;
        }
        ans += blocking_flow(x, y, INF);
    }
    return ans;
}
int blocking_flow(int x, int y, int limit)
{
    if( x == y )
    {
        return limit;
    }
    int ans = 0, i, temp, s;
    list *pp;
    for( pp = t[x] ; pp ; pp = pp -> next )
    {
        if(pp -> w)
        {
            i = pp -> x;
            if( level[i] <= level[x] )
            {
                continue;
            }
            s = ( limit > pp -> w ) ? pp -> w : limit;
            temp = blocking_flow(i, y, s);
            if(!temp)
            {
                continue;
            }
            ans += temp;
            limit -= temp;
            pp -> w -= temp;
            *(pp -> p) += temp;
            if(!limit)
            {
                break;
            }
        }
    }
    return ans;
}
int main()
{
    int M, x, y, z, f, i, j, k;
    long long ans = 1;
    scanf("%d%d", &N, &M);
    for( i = 0 ; i < M ; i++ )
    {
        scanf("%d%d%d", &x, &y, &z);
        table[x-1][y-1] += z;
        table[y-1][x-1] += z;
    }
    for( i = 0 ; i < N - 1 ; i++ )
    {
        for( j = i + 1 ; j < N ; j++ )
        {
            if(table[i][j])
            {
                insert_edge(i, j, table[i][j]);
            }
        }
    }
    for( i = 0 ; i < N ; i++ )
    {
        for( j = 0 ; j < N ; j++ )
        {
            GH[i][j] = INF;
        }
    }
    for( i = 1 ; i < N ; i++ )
    {
        f = min_cut(i, parent[i]);
        for( j = i + 1 ; j < N ; j++ )
        {
            if( level[j] != -1 && parent[j] == parent[i] )
            {
                parent[j] = i;
            }
        }
        GH[i][parent[i]] = GH[parent[i]][i] = f;
        for( j = 0 ; j < i ; j++ )
        {
            GH[i][j] = GH[j][i] = min(f, GH[parent[i]][j]);
        }
    }
    for( i = 0 ; i < N - 1 ; i++ )
    {
        for( j = i + 1 ; j < N ; j++ )
        {
            ans = GH[i][j] * ans % MOD;
        }
    }
    printf("%lld", ans);
    return 0;
}