/**
 * Edmonds-Karp algorithm with O(V³E) complexity
 *
 * This implementation is a slightliy modified source from Wikipedia. See
 * http://en.wikipedia.org/wiki/Edmonds_karp
 */
class MaxFlow {

    public static final int UNVISITED = 0, VISITED = 1;

    private int[][] res_capacity; // Residual capacity
    private int[] parent; // Parent node in Breadth First Search (BFS)
    private int[] mark; // BFS: Already visited?
    private int[] min_capacity; // Minimal flow
    private int size; // Number of nodes
    private int sink;

    public MaxFlow() {
    }

    public int getMaxflow(int[][] graphMatrix, int source, int sink) {
        this.sink = sink;
        this.size = graphMatrix.length;

        int max_flow = 0; // THE max flow for which we are doing this
        // circus

        int[][] flow = new int[size][size]; // Our flow
        res_capacity = new int[size][size]; // Remaining capacity

        parent = new int[size];
        min_capacity = new int[size];
        mark = new int[size];

        // Before we start, all capacities are residual
        // System.arraycopy may be faster: see http://www.javaspecialists.eu/archive/Issue124.html
       
        // The following is wrong, as Feri in the comments has found out.
        // clone() is one-dimensional! *pats-head*
        // res_capacity=graphMatrix.clone();
        //
        //Faster:
        for (int i = 0; i < size; i++) {
            System.arraycopy(graphMatrix[i], 0, res_capacity[i], 0, size);
        }

        // Search in BFS manner through the graph, Path by Path
        while (BFS(source)) {
            max_flow += min_capacity[sink];
            int v = sink, u;
            while (v != source) {
                u = parent[v];
                flow[u][v] += min_capacity[sink];
                flow[v][u] -= min_capacity[sink];
                res_capacity[u][v] -= min_capacity[sink];
                res_capacity[v][u] += min_capacity[sink];
                v = u;
            }
        }
        return max_flow;
    }

    /**
     * Breadth First Search in O(V²)
     *
     * @param source
     *            The source node
     */
    private boolean BFS(int source) {
        int first, last; // Queue pointers
        int[] queue; // Queue pointers

        queue = new int[size];
        for (int i = 0; i < size; i++) {
            mark[i] = UNVISITED;
            min_capacity[i] = Integer.MAX_VALUE;
        }

        first = last = 0;
        queue[last++] = source;
        mark[source] = VISITED;

        while (first != last) { // While "queue" not empty.
            int v = queue[first++];
            for (int u = 0; u < size; u++)
                if (mark[u] == UNVISITED && res_capacity[v][u] > 0) {
                    min_capacity[u] = Math.min(min_capacity[v],
                            res_capacity[v][u]);
                    parent[u] = v;
                    mark[u] = VISITED;
                    if (u == sink)
                        return true;
                    queue[last++] = u;
                }
        }
        return false;
    }
}