1.) Question 2 correction. import java.util.*; public c

1.) Question 2 correction
import java.util.*;
public class MaximumFlow
{
static class Edge
{
int t, rev, cap, f;
public Edge(int t, int rev, int cap)
{
this.t = t;
this.rev = rev;
this.cap = cap;
}
}
//lets use the ArrayList data structure to create our graph
public static List<Edge>[] createGraph( int nodes)
{
List<Edge>[] graph = new List[nodes];//an array havind arraylist and os
size of provided nodes
for(int i = 0; i < nodes; i++)
{
graph[i] = new ArrayList<>();
}
return graph;
}
public static void addEdge(List<Edge>[] graph, int src, int dst, int cap)
//graph= our graph
// src = source "s";
//dst = sink "t";
//cap = capacity
{
graph[src].add(new Edge(dst, graph[dst].size(), cap));
graph[dst].add( new Edge(src, graph[src].size(), cap));
}
static boolean dinicBFS(List<Edge>[] graph, int src, int dest, int[] dist)
//dist = distance(path).
{
//by default lets alllocate distances to -1
Arrays.fill( dist, -1);
dist[src] = 0;//from itself =0

int [] q = new int[graph.length];
int sizeq = 0;
q[sizeq++] = src;
for(int i = 0; i < sizeq; i++)
{
int u = q[i];
for(Edge e : graph[u])
{
if(dist[e.t] < 0 && e.f < e.cap)
{
dist[e.t] = dist[u] + 1;
q[sizeq++] = e.t;
}
}
}
return dist[dest] >= 0;
}
static int dinicDFS(List<Edge>[] graph, int [] ptr, int [] dist,int dest,int u, int f)
{
if( u== dest)
return f;
for(;ptr[u] < graph[u].size();++ptr[u])
{
Edge e = graph[u].get(ptr[u]);
if(dist[e.t] == dist[u] + 1 && e.f < e.cap)
{
int df = dinicDFS(graph, ptr,dist,dest, e.t, Math.min(f, e.cap
- e.f) );
if(df > 0)
{
e.f += df;
graph[e.t].get(e.rev).f -= df;
return df;
}
}
}
return 0;
}
public static int maxFlow(List<Edge>[] graph, int src, int dest)
{
int flow = 0;

int [] dist = new int[graph.length];
while(dinicBFS(graph, src, dest, dist))
{
int [] ptr = new int[graph.length];
while(true)
{
int df = dinicDFS(graph,ptr, dist, dest, src,
Integer.MAX_VALUE);
if( df == 0)
break;
flow += df;
}
}
return flow;
}
static int RandomIntegers(int min,int max)
{
Random r = new Random();
return r.nextInt((max - min) + 1) + min;
}
//Driver program with an example
public static void main(String[] args)
{
List<Edge>[] g =createGraph(12);
int [] nodes = new int[12];//this refers to nodes inclusive
//of source and vertex
for(int i = 0; i < 12;i++)
{
nodes[i] = RandomIntegers(4,12);
}
for(int i = 1,j = 1; i < 12 && j < 12; i++, j++)
{
addEdge(g,nodes[i],nodes[j],RandomIntegers(5,20));//allocating
//capacities randomly
}
System.out.println(maxFlow(g,0,11));//returns maxFlow else zero if
//none found
}
}