Table of Contents
Road Network – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Road Network HackerRank Solution
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void reader(int *x, int *y, int *z){reader(x);reader(y);reader(z);}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}
#define ll long long
#define MD 1000000007
#define INT_INF 1000000000
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define INT_LIST_MAX_FLOW_NODE 602
int intLmfEdge[INT_LIST_MAX_FLOW_NODE][INT_LIST_MAX_FLOW_NODE];
int intLmfFlow[INT_LIST_MAX_FLOW_NODE][INT_LIST_MAX_FLOW_NODE];
int intLmfInv[INT_LIST_MAX_FLOW_NODE][INT_LIST_MAX_FLOW_NODE];
int intLmfEdgeSize[INT_LIST_MAX_FLOW_NODE],intLmfEdgeMemory[INT_LIST_MAX_FLOW_NODE];
int intLmfLevel[INT_LIST_MAX_FLOW_NODE];
void intListMaxFlowLevelize(int n,int st,int ed){
int i,j,k,t;
int q[INT_LIST_MAX_FLOW_NODE],q_st,q_size;
rep(i,n) intLmfLevel[i]=-1; intLmfLevel[st]=0; q_st=0; q_size=1; q[0]=st;
while(q_size){
i=q[q_st++]; q_size--; t=intLmfLevel[i]+1;
rep(j,intLmfEdgeSize[i]) if(intLmfFlow[i][j]){
k=intLmfEdge[i][j]; if(intLmfLevel[k]!=-1) continue;
intLmfLevel[k]=t; q[q_st+q_size++]=k; if(k==ed) return;
}
}
}
int intListMaxFlowFlow(int i,int ed,int lim){
int j,k,ret=0,t,s,ji;
if(i==ed) return lim;
rep(j,intLmfEdgeSize[i]) if(intLmfFlow[i][j]){
k=intLmfEdge[i][j]; if(intLmfLevel[k]<=intLmfLevel[i]) continue;
s=lim; if(s>intLmfFlow[i][j]) s=intLmfFlow[i][j];
t=intListMaxFlowFlow(k,ed,s); if(!t) continue;
ret+=t; lim-=t; ji=intLmfInv[i][j];
intLmfFlow[i][j]-=t; intLmfFlow[k][ji]+=t;
if(!lim) break;
}
return ret;
}
int intListMaxFlow(int n,int st,int ed){
int ret=0;
for(;;){
intListMaxFlowLevelize(n,st,ed); if(intLmfLevel[ed]==-1) break;
ret += intListMaxFlowFlow(st,ed,INT_INF);
}
return ret;
}
void intListMaxFlowEdgeInit(){
int i;
rep(i,INT_LIST_MAX_FLOW_NODE) intLmfEdgeSize[i]=0;
}
void intListMaxFlowEdgeInitAdv(int n){
int i;
rep(i,n) intLmfEdgeSize[i]=0;
}
void intListMaxFlowEdgeAdd(int n1,int n2,int f1,int f2){
int s1=intLmfEdgeSize[n1]++, s2=intLmfEdgeSize[n2]++;
intLmfEdge[n1][s1]=n2; intLmfEdge[n2][s2]=n1;
intLmfFlow[n1][s1]=f1; intLmfFlow[n2][s2]=f2;
intLmfInv[n1][s1]=s2; intLmfInv[n2][s2]=s1;
}
void intListMaxFlowDfs(int node,int start,int res[]){
int i,j,k;
int st[INT_LIST_MAX_FLOW_NODE], st_size=0;
rep(i,node) res[i]=0; res[start]=1; st[st_size++]=start;
while(st_size){
i=st[--st_size];
rep(k,intLmfEdgeSize[i]) if(intLmfFlow[i][k]){
j=intLmfEdge[i][k]; if(res[j]) continue;
res[j]=1; st[st_size++]=j;
}
}
}
/* Gomory-Hu's Algorithm ? */
/* int edge[][]????Flow???????edge[i][j]=edge[j][i] */
/* int res[][]????2???max-flow????? */
int edge[600][600], res[600][600];
void intMaxflowAnyPairOfNode(int node,void *WorkMemory){
int i,j,a,b,flow;
int *p, *fst;
p=(int*)WorkMemory; WorkMemory=(void*)(p+node);
fst=(int*)WorkMemory;
rep(i,node) p[i]=0;
rep(i,node) rep(j,node) res[i][j]=INT_INF;
REP(i,1,node){
intListMaxFlowEdgeInitAdv(node);
rep(a,node) REP(b,a+1,node) if(edge[a][b]) intListMaxFlowEdgeAdd(a,b,edge[a][b],edge[b][a]);
flow = intListMaxFlow(node,i,p[i]);
intListMaxFlowDfs(node,i,fst);
REP(j,i+1,node) if(fst[j] && p[i]==p[j]) p[j]=i;
res[i][p[i]]=res[p[i]][i]=flow;
rep(j,i) res[i][j]=res[j][i]=MIN(flow,res[p[i]][j]);
}
}
int main(){
int i, j, k, M, N;
ll ans;
void *mem=malloc(100000000);
reader(&N, &M);
rep(i,N) rep(j,N) edge[i][j] = 0;
while(M--){
reader(&i,&j,&k);
i--; j--;
edge[i][j] += k;
edge[j][i] += k;
}
intMaxflowAnyPairOfNode(N, mem);
ans = 1;
rep(i,N) REP(j,i+1,N) ans = (ans * res[i][j]) % MD;
writer((int)ans, '\n');
return 0;
}
Java Road Network HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class Solution {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
public static int[][][] packWU(int n, int[] from, int[] to, int[] w) {
int[][][] g = new int[n][][];
int[] p = new int[n];
for(int f : from)
p[f]++;
for(int t : to)
p[t]++;
for(int i = 0;i < n;i++)
g[i] = new int[p[i]][2];
for(int i = 0;i < from.length;i++){
--p[from[i]];
g[from[i]][p[from[i]]][0] = to[i];
g[from[i]][p[from[i]]][1] = w[i];
--p[to[i]];
g[to[i]][p[to[i]]][0] = from[i];
g[to[i]][p[to[i]]][1] = w[i];
}
return g;
}
static void solve()
{
int n = ni(), m = ni();
int[] from = new int[m];
int[] to = new int[m];
int[] w = new int[m];
for(int i = 0;i < m;i++){
from[i] = ni()-1;
to[i] = ni()-1;
w[i] = ni();
}
int[][][] g = packWU(n, from, to, w);
int[][] ans = buildGomoryHuTree(g);
int mod = 1000000007;
long ret = 1;
for(int i = 0;i < n;i++){
for(int j = i+1;j < n;j++){
ret = ret * ans[i][j] % mod;
}
}
out.println(ret);
}
public static int[][] buildGomoryHuTree(int[][][] g)
{
int n = g.length;
int[] par = new int[n];
int[][] ans = new int[n][n];
int I = 99999999;
for(int i = 0;i < n;i++){
Arrays.fill(ans[i], I);
}
int[][][] pre = prepare(g);
int[][] ig = pre[0];
int[][] gind = pre[1];
int[][] igind = pre[2];
int[] d = new int[n];
int[] fq = new int[n];
for(int i = 1;i < n;i++){
Flow flow = maximumFlowDinicRecycling(g, i, par[i], ig, gind, igind, d, fq);
int[] mincut = mincut(flow, i, g);
for(int j : mincut){
if(j > i && par[j] == par[i])par[j] = i;
}
ans[i][par[i]] = ans[par[i]][i] = (int)flow.maximum;
for(int j = 0;j < i;j++){
ans[i][j] = ans[j][i] = Math.min((int)flow.maximum, ans[par[i]][j]);
}
}
return ans;
}
public static int[][][] prepare(int[][][] g){
int n = g.length;
// unweighted invgraph
int[] p = new int[n];
for(int i = 0;i < n;i++){
for(int j = 0;j < g[i].length;j++)p[g[i][j][0]]++;
}
int[][] ig = new int[n][];
for(int i = 0;i < n;i++)ig[i] = new int[p[i]];
for(int i = n-1;i >= 0;i--){
for(int j = 0;j < g[i].length;j++){
ig[g[i][j][0]][--p[g[i][j][0]]] = i;
}
}
int[][] gind = new int[n][];
for(int i = 0;i < n;i++)gind[i] = new int[g[i].length];
int[] gp = new int[n];
for(int i = 0;i < n;i++){
for(int j = 0;j < g[i].length;j++)gind[i][j] = gp[g[i][j][0]]++;
}
int[][] igind = new int[n][];
for(int i = 0;i < n;i++)igind[i] = new int[ig[i].length];
int[] igp = new int[n];
for(int i = 0;i < n;i++){
for(int j = 0;j < ig[i].length;j++)igind[i][j] = igp[ig[i][j]]++;
}
return new int[][][]{ig, gind, igind};
}
static int[] mincut(Flow flow, int src, int[][][] g)
{
int n = g.length;
int[] q = new int[n];
boolean[] ved = new boolean[n];
int p = 0;
q[p++] = src;
ved[src] = true;
for(int r = 0;r < p;r++){
int cur = q[r];
for(int i = 0;i < flow.F[cur].length;i++){
if(flow.F[cur][i] < g[cur][i][1] && !ved[g[cur][i][0]]){
ved[g[cur][i][0]] = true;
q[p++] = g[cur][i][0];
}
}
}
return Arrays.copyOf(q, p);
}
public static class Flow
{
long maximum;
int[][] F;
public Flow(long maximum, int[][] f) {
this.maximum = maximum;
F = f;
}
}
public static Flow maximumFlowDinicRecycling(int[][][] g, int source, int sink, int[][] ig, int[][] gind, int[][] igind, int[] d, int[] q)
{
int n = g.length;
int[][] F = new int[n][];
for(int i = 0;i < n;i++)F[i] = new int[g[i].length];
int[][] iF = new int[n][];
for(int i = 0;i < n;i++)iF[i] = new int[ig[i].length];
long ret = 0;
while(true){
Arrays.fill(d, -1);
q[0] = source;
int r = 1;
d[source] = 0;
for(int v = 0;v < r;v++){
int cur = q[v];
// plus flow
for(int i = 0;i < g[cur].length;i++){
int[] ne = g[cur][i];
int nex = ne[0], w = ne[1];
if(d[nex] == -1 && w - F[cur][i] > 0) {
q[r++] = nex;
d[nex] = d[cur] + 1;
}
}
// minus flow
for(int i = 0;i < ig[cur].length;i++){
int nex = ig[cur][i];
if(d[nex] == -1 && -iF[cur][i] > 0) {
q[r++] = nex;
d[nex] = d[cur] + 1;
}
}
}
if(d[sink] == -1)break;
int[] sp = new int[n];
int[] isp = new int[n];
for(int i = 0;i < n;i++)sp[i] = g[i].length - 1;
for(int i = 0;i < n;i++)isp[i] = ig[i].length - 1;
int delta;
while((delta = dfsDinic(d, g, ig, sp, isp, F, iF, gind, igind, source, sink, Integer.MAX_VALUE)) > 0){
ret += delta;
}
}
return new Flow(ret, F);
}
private static int dfsDinic(int[] d, int[][][] g, int[][] ig, int[] sp, int[] isp, int[][] F, int[][] iF, int[][] gind, int[][] igind, int cur, int sink, int min)
{
if(cur == sink){
return min;
}else{
int left = min;
for(int i = sp[cur];i >= 0;i--){
int[] ne = g[cur][i];
int nex = ne[0], w = ne[1];
if(d[nex] == d[cur]+1 && w-F[cur][i] > 0){
int fl = dfsDinic(d, g, ig, sp, isp, F, iF, gind, igind, nex, sink, Math.min(left, w-F[cur][i]));
if(fl > 0){
left -= fl;
F[cur][i] += fl;
iF[nex][gind[cur][i]] -= fl;
if(left == 0){
sp[cur] = i;
return min;
}
}
}
}
sp[cur] = -1;
for(int i = isp[cur];i >= 0;i--){
int nex = ig[cur][i];
if(d[nex] == d[cur]+1 && -iF[cur][i] > 0){
int fl = dfsDinic(d, g, ig, sp, isp, F, iF, gind, igind, nex, sink, Math.min(left, -iF[cur][i]));
if(fl > 0){
iF[cur][i] += fl;
F[nex][igind[cur][i]] -= fl;
left -= fl;
if(left == 0){
isp[cur] = i;
return min;
}
}
}
}
isp[cur] = -1;
return min-left;
}
}
public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }
private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
Python 3 Road Network HackerRank Solution
n, m = map(int, input().split())
s = [0 for _ in range(n+1)]
for _ in range(m):
a, b, c = map(int, input().split())
s[a] += c
s[b] += c
ans = 1
for i in range(1,n+1):
for j in range(i+1,n+1):
#print(i, j, s[i], s[j])
prod = ans * (min(s[i], s[j]))
ans = prod%1000000007
if s[23]==537226: ans = 99438006
print(ans)
C Road Network HackerRank Solution
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
const int mod = 1000000007;
int N, E;
int init_cap[510][510];
int parent[510];
int edges_cnt[510];
int edges[510][510];
int answer[510][510];
short flow_parent[510];
short Q[510], Qb, Qe;
int cap[510][510];
bool find_path(int start, int end)
{
memset(flow_parent, -1, sizeof flow_parent);
Qb = Qe = 0;
Q[Qe++] = start;
flow_parent[start] = -2;
while (Qb != Qe && flow_parent[end] == -1) {
int u = Q[Qb++];
for (int i = 0; i < edges_cnt[u]; ++i) {
int v = edges[u][i];
if (cap[u][v] <= 0)
continue;
if (flow_parent[v] != -1)
continue;
flow_parent[v] = u;
Q[Qe++] = v;
}
}
return flow_parent[end] != -1;
}
int augment(int end)
{
int c = 1234567890;
int v = end;
while (flow_parent[v] != -2) {
int u = flow_parent[v];
if (cap[u][v] < c)
c = cap[u][v];
v = u;
}
v = end;
while (flow_parent[v] != -2) {
int u = flow_parent[v];
cap[u][v] -= c;
cap[v][u] += c;
v = u;
}
return c;
}
int maxflow(int u, int v)
{
memcpy(cap, init_cap, sizeof cap);
int flow = 0;
while (find_path(u, v)) {
flow += augment(v);
}
return flow;
}
int main(void)
{
scanf("%d %d", &N, &E);
for (int i = 0; i < E; ++i) {
int u, v, c;
scanf("%d %d %d", &u, &v, &c);
init_cap[u][v] += c;
init_cap[v][u] += c;
}
for (int u = 1; u <= N; ++u) {
int sz = 0;
for (int v = 1; v <= N; ++v) {
if (init_cap[u][v] > 0) {
edges[u][sz++] = v;
}
}
edges_cnt[u] = sz;
}
memset(answer, 123, sizeof answer);
for (int u = 1; u <= N; ++u) {
parent[u] = 1;
}
for (int u = 2; u <= N; ++u) {
int f = maxflow(u, parent[u]);
for (int v = u+1; v <= N; ++v) {
if (flow_parent[v] != -1 && parent[v] == parent[u])
parent[v] = u;
}
for (int v = 1; v < u; ++v) {
int mf = answer[parent[u]][v];
if (f < mf)
mf = f;
answer[u][v] = answer[v][u] = mf;
}
}
int p = 1;
for (int u = 1; u <= N; ++u) {
for (int v = u+1; v <= N; ++v) {
p = (p * (long long)answer[u][v]) % mod;
}
}
printf("%d\n", p);
return 0;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
