HackerRank Road Network problem solution YASH PAL, 31 July 2024 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() {“mode”:”full”,”isActive”:false} 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(); } } {“mode”:”full”,”isActive”:false} 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; } {“mode”:”full”,”isActive”:false} 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; } {“mode”:”full”,”isActive”:false} algorithm coding problems