Given a graph with N vertices numbered 1 to N and M edges, the task is to find the max flow from vertex 1 to vertex N.
Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains two space separated integers N and M . Then in the next line are M space separated triplets x, y, z denoting an undirected edge from x to y with a flow capacity of z.
Output:
For each test case in a new line print a single integer denoting the maximum flow between 1 to N.
Constraints:
1<=T<=100
1<=N,M<=1000
Example:
Input:
2
5 4
1 2 1 3 2 2 4 2 3 2 5 5
4 4
1 2 8 1 3 10 2 4 2 3 4 3
Output:
1
5
class Solution {
static int totalFlow;
// The input is adjacency matrix graph
// It does not matter whether the input is directed or undirected
// If it is undirected just assume 1 flow as back flow of other
public static int maxFlow(int[][] graph) {
totalFlow = 0;
while (BFS(graph, 0, graph.length - 1)) {
// Nothing to do here
}
return totalFlow;
}
public static boolean BFS(int[][] graph, int source, int target) {
boolean[] visited = new boolean[graph.length];
int[] parent = new int[graph.length];
for (int i = 0; i < graph.length; i++)
parent[i] = i;
Queue<Integer> q = new LinkedList<>();
visited[source] = true;
boolean isReachable = false;
q.add(source);
while (q.size() != 0) {
int node = q.poll();
if (node == target) {
isReachable = true;
break;
}
// Now we will go through all the neighbors and add
// neighbors with edge flow > 0 && !visited
for (int i = 0; i < graph.length; i++) {
if (graph[node][i] > 0 && !visited[i]) {
visited[i] = true;
q.add(i);
parent[i] = node;
}
}
}
if (isReachable) {
// Finding the min flow in the path from source to target
int minFlow = Integer.MAX_VALUE;
int node = target;
while (node != parent[node]) {
minFlow = Math.min(minFlow, graph[parent[node]][node]);
node = parent[node];
}
// Now we need to add this flow to our answer
// aswell as remove it from original flow and add to to back flow
totalFlow += minFlow;
node = target;
while (node != parent[node]) {
graph[parent[node]][node] -= minFlow;
graph[node][parent[node]] += minFlow;
node = parent[node];
}
}
return isReachable;
}
}