FASTFLOW SPOJ (Maxflow Dinic's Algorithm) Solution JAVA

Algorithm : Dinic's Fastflow

Source :

import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.InputMismatchException;

public class FASTFLOW {
    static final int INF = 0x7fffffff;
    int maxnodes, maxedges, src, dest, edges;
    int[] top, work, Q;
    int[] head, prev, flow, cap, dist;
    boolean marked;

    public void init(int maxnodes, int maxedges) {
        this.maxnodes = maxnodes;
        this.maxedges = maxedges;
        top = new int[maxnodes];
        work = new int[maxnodes];
        Q = new int[maxnodes];
        dist = new int[maxnodes];

        head = new int[maxedges];
        prev = new int[maxedges];

        flow = new int[maxedges];
        cap = new int[maxedges];

        clear();
    }

    public void clear() {
        Arrays.fill(top, -1);
        edges = 0;
    }

    public void addEdge(int u, int v, int capacity) {
        head[edges] = v;
        cap[edges] = capacity;
        flow[edges] = 0;
        prev[edges] = top[u];
        top[u] = edges++;
         
        head[edges] = u;
        cap[edges] = 0;
        flow[edges] = 0;
        prev[edges] = top[v];
        top[v] = edges++;
    }

    boolean dinic_bfs() {
        Arrays.fill(dist, -1);
        dist[src] = 0;
        int sizeQ = 0;
        Q[sizeQ++] = src;
        for (int i = 0; i < sizeQ; ++i) {
            int u = Q[i];
            for (int e = top[u]; e >= 0; e = prev[e]) {
                int v = head[e];
                if (flow[e] < cap[e] && dist[v] < 0) {
                    dist[v] = dist[u] + 1;
                    Q[sizeQ++] = v;
                }
            }
        }
        return dist[dest] >= 0;
    }

    int dinic_dfs(int u, int f) {
        if (u == dest) {
            return f;
        }
        for (int e = work[u]; e >= 0; work[u] = e = prev[e]) {
            int v = head[e];
            if (flow[e] < cap[e] && dist[v] == dist[u] + 1) {
                int df = dinic_dfs(v, Math.min(f, cap[e] - flow[e]));
                if (df > 0) {
                    flow[e] += df;
                    flow[e^1] -= df;
                    return df;
                }
            }
        }
        return 0;
    }

    public double maxFlow(int src, int dest) {
        this.src = src;
        this.dest = dest;
        double flow = 0;
        while (dinic_bfs()) {
            System.arraycopy(top, 0, work, 0, maxnodes);
            while (true) {
                int df = dinic_dfs(src, INF);
                if (df == 0) {
                    break;
                }
                flow += df;
            }
        }
        return flow;
    }
     
    
    public static void main(String[] args){ 
        FASTFLOW instance = new FASTFLOW();
        
        
        int N, M;
        N = IO.nextInt();
        M = IO.nextInt(); 
        instance.init(N, M*4); 
        int sourceI = 0, sinkI = N-1; 

        for(int i=0;i<M;++i){
            int x, y, c;
            x = IO.nextInt()-1;
            y = IO.nextInt()-1; 
            c = IO.nextInt(); 

            if(x==y)continue;

            instance.addEdge(x, y, c);
            instance.addEdge(y, x, c);
        }


        System.out.printf("%.0f\n", (instance.maxFlow(sourceI, sinkI))); 
    }
    
    private static class IO {

        private static InputStream stream = System.in;
        private static byte[] buf = new byte[1024];
        private static int curChar, numChars;

        private static int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public static int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public static char nextChar() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            return (char) c;
        }

        private static boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private static void println(Object... a) {
            for (Object o : a) {
                System.out.print(o);
            }
            System.out.println();
        }
    }
}