Problem: https://www.spoj.com/problems/FASTFLOW/
I am using Edmund Karp. Example passes, not sure why submission fails with wrong answer.
Can someone please help?
import java.util.*;
public class Main {
public static void main(String[] args) {
try {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
// System.out.println(N + " " + M);
List<int[]> edges = new ArrayList<>();
int dupCount = 0;
while (M > 0) {
int fr = sc.nextInt();
int to = sc.nextInt();
int wt = sc.nextInt();
edges.add(new int[]{fr, to, wt});
if (fr == to) ++dupCount;
--M;
// System.out.println(fr + " " + to + " " + wt);
}
Solution soln = new Solution();
System.out.println(soln.maxFlow(edges, N, dupCount));
} catch(Exception e) {}
}
}
class Solution {
private int N, T, S;
private int[][] graph;
public long maxFlow(List<int[]> edges, int n, int dupCount) {
N = n + n;
T = n;
S = 1;
int dummyV = n+1;
int[][] dummyVMem = new int[N+2][N+2];
graph = new int[N+2][N+2];
for(int[] e : edges) {
if(e[0] == e[1]) continue;
if(dummyVMem[e[0]][e[1]] == 0 && dummyVMem[e[1]][e[0]] == 0) {
graph[e[0]][e[1]] = e[2];
graph[e[1]][dummyV] = e[2];
graph[dummyV][e[0]] = e[2];
dummyVMem[e[1]][e[0]] = dummyV;
++dummyV;
} else if (dummyVMem[e[0]][e[1]] != 0) {
graph[e[1]][e[0]] += e[2];
int tmp = dummyVMem[e[0]][e[1]];
graph[e[0]][tmp] += e[2];
graph[tmp][e[1]] += e[2];
} else {
graph[e[0]][e[1]] += e[2];
int tmp = dummyVMem[e[1]][e[0]];
graph[e[1]][tmp] += e[2];
graph[tmp][e[0]] += e[2];
}
}
Integer[] path = new Integer[N+1];
long flow = bfs(S, T, path);
long maxFlow = 0;
while(flow > 0) {
maxFlow += flow;
int to = T;
while(to != S) {
graph[path[to]][to] -= flow;
graph[to][path[to]] += flow;
// System.out.print(to + " <- " + path[to] + " | ");
to = path[to];
}
// System.out.println(" " + flow);
path = new Integer[N+1];
flow = bfs(S, T, path);
}
return maxFlow;
}
private long bfs(int s, int t, Integer[] path) {
ArrayDeque<long[]> que = new ArrayDeque<>();
que.addLast(new long[]{s, Integer.MAX_VALUE});
path[s] = s;
while(!que.isEmpty()) {
long[] node = que.removeFirst();
int pa = (int)node[0];
long flow = node[1];
for(int child=1; child<=N; ++child) {
if(graph[pa][child] == 0 || path[child] != null) continue;
path[child] = pa;
flow = Math.min(flow, graph[pa][child]);
if(child == t) return flow;
else que.addLast(new long[]{child, flow});
}
}
return 0;
}
}