BANKROB - SPOJ Solution MAXFLOW-Ford-Fulkerson

Algorithm:

1. Split each node into two nodes. Node start and node end. Connect these by links with capacity = 1 from start to end node. "Source node-start" connects to "source node-end" with Infinite capacity. Same with target node.

2. If the input is, for example, 2 - 4 for an edge, connect "node 2-end" to "node-4 start" and "node 4-end" to "node 2-start" with capacity = Infinite. Do this for all input edges.

3. Run Ford-Fulkerson.

4. The number of augmenting paths found is the solution.

Code (Java) :

import java.io.*;
import java.util.*;
 
public class MAXFLOWWC {
    static int s, t, V, E;
    static ArrayList<ArrayList<Edge>> g;  
    public static void main(String[] args) throws Exception{
        int[] line1 = IO.nextIntArray(2, " ");
        int[] line2 = IO.nextIntArray(2, " ");
        
        V = (line1[1])*2+1;
        E = line1[2];
        s = line2[1]*2-1;
        t = line2[2]*2-1; 
        g = new ArrayList<>();
        for(int i=0;i<V;++i)g.add(new ArrayList<>()); 
        int data[][] = IO.next2dInt(E, 2, " "); 
        
        for(int i=1;i<V;i+=2){ 
            int cap = 1;
            if(i==s || i==t)cap = Integer.MAX_VALUE;
            g.get(i).add(new Edge(i, i+1, cap));
            g.get(i+1).add(new Edge(i+1, i, cap));
        }
        
        for(int i=1;i<data.length;++i){
            int[] line = data[i];
            int cap = Integer.MAX_VALUE; 
            
            line[1] = line[1]*2;
            line[2] = line[2]*2; 
            
            Edge edge1 = new Edge(line[1], line[2]-1, cap); // 2-3
            Edge edge2 = new Edge(line[2], line[1]-1, cap); // 4-1 
            g.get(line[1]).add(edge1); 
            g.get(line[1]-1).add(edge2);
            g.get(line[2]-1).add(edge1); 
            g.get(line[2]).add(edge2); 
        }
        
        Fulkerson();
        IO.println(augPaths);
    }
    
    static int augPaths;
    
    public static void Fulkerson(){
        int flow=0;
        Edge[] path = hasAugmentingPath(); 
        while(path[t]!=null){
            augPaths++;
            int min = Integer.MAX_VALUE;   
            for(int i=t;i!=s;i = path[i].other(i)){ 
                if(path[i].capacityTo(i)<min) min = path[i].capacityTo(i);  
            } 
            flow+=min;
            for(int i=t;i!=s;i=path[i].other(i)) path[i].adjustFlow(i, min);  
            path = hasAugmentingPath();
        } 
    }
    
    
    public static Edge[] hasAugmentingPath(){ 
        Edge[] path = new Edge[V];
        Arrays.fill(path, null);
        Queue<Integer> q = new LinkedList<>();
        q.add(s);
        
        boolean marked[] = new boolean[V]; 
        marked[s] = true;
        boolean stop = false;
        while(!q.isEmpty()){
            int c = q.poll();  
            for(Edge edge:g.get(c)){  
                if(edge.to!=c && marked[edge.to]) continue;
                if(edge.capacityTo(edge.other(c))!=0){ 
                    q.add(edge.other(c)); 
                    marked[edge.other(c)] = true; 
                    if(path[edge.other(c)]==null)path[edge.other(c)] = edge; 
                    if(edge.other(c)==t){stop = true;break;}
                }
            }
            if(stop)break;
        } 
        return path;
    }
    
    static class Edge{
        int from, to, capacity, flow;
        Edge(int from, int to, int capacity){
            this.from = from;
            this.to = to;
            this.capacity = capacity;
            flow = 0;
        }
        int other(int e){
            if(e==from)return to;
            else return from;
        }
        int capacityTo(int v){
            if(v==to)return (capacity-flow);
            else return flow;
        }
        void adjustFlow(int v, int flow){
            if(v==to)this.flow += flow;
            else this.flow -= flow;
        }
        public String toString(){return "["+from+"-"+to+":"+flow+"/"+capacity+"]";}
    }
    static class IO {

        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        public static int[][] next2dInt(int rows, int cols, String seperator) throws Exception {
            int[][] arr = new int[rows + 1][cols + 1];
            for (int i = 1; i <= rows; ++i) {
                arr[i] = nextIntArray(cols, seperator);
            }
            return arr;
        }

        public static int[] nextIntArray(int nInts, String seperator) throws IOException {
            String ints = br.readLine();
            String[] sArray = ints.split(seperator);
            int[] array = new int[nInts + 1];
            for (int i = 1; i <= nInts; ++i) {
                array[i] = Integer.parseInt(sArray[i - 1]);
            }
            return array;
        }

        public static long[] nextLongArray(int nLongs, String seperator) throws IOException {
            String longs = br.readLine();
            String[] sArray = longs.split(seperator);
            long[] array = new long[nLongs + 1];
            for (int i = 1; i <= nLongs; ++i) {
                array[i] = Long.parseLong(sArray[i - 1]);
            }
            return array;
        }

        public static double[] nextDoubleArray(int nDoubles, String seperator) throws IOException {
            String doubles = br.readLine();
            String[] sArray = doubles.split(seperator);
            double[] array = new double[nDoubles + 1];
            for (int i = 1; i <= nDoubles; ++i) {
                array[i] = Double.parseDouble(sArray[i - 1]);
            }
            return array;
        }

        public static char[] nextCharArray(int nChars, String seperator) throws IOException {
            String chars = br.readLine();
            String[] sArray = chars.split(seperator);
            char[] array = new char[nChars + 1];
            for (int i = 1; i <= nChars; ++i) {
                array[i] = sArray[i - 1].charAt(0);
            }
            return array;
        }

        public static int nextInt() throws IOException {
            String in = br.readLine();
            return Integer.parseInt(in);
        }

        public static double nextDouble() throws IOException {
            String in = br.readLine();
            return Double.parseDouble(in);
        }

        public static long nextLong() throws IOException {
            String in = br.readLine();
            return Long.parseLong(in);
        }

        public static int nextChar() throws IOException {
            String in = br.readLine();
            return in.charAt(0);
        }

        public static String nextString() throws IOException {
            return br.readLine();
        }

        public static void print(Object... o) {
            for (Object os : o) {
                System.out.print(os);
            }
        }

        public static void println(Object... o) {
            for (Object os : o) {
                System.out.print(os);
            }
            System.out.print("\n");
        }

        public static void printlnSeperate(String seperator, Object... o) {
            StringBuilder sb = new StringBuilder();
            sb.delete(sb.length() - seperator.length(), sb.length());
            System.out.println(sb);
        }
    } 
}