TAXI SPOJ (Maxflow - Maximum Bipartite Matching - Dinic's Algorithm) Solution JAVA

Algorithm : 

1. Add source and sink nodes.
2. Add link from source to PERSONi node.
3. Add link from TAXIi to sink node.
4. Add a link from Pi to Ti if it is possible for the taxi to cover the block distance between itself and the person within the given time.
5. Run Dinic's algorithm to compute the maxflow.

Source:

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

public class TAXI {
    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 int maxFlow(int src, int dest) {
        this.src = src;
        this.dest = dest;
        int 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;
    }
    
    static class Point{
        int x, y;
        Point(int a, int b){
            x = a; y = b;
        }
        
        int distTo(Point b){
            return Math.abs(this.x-b.x)+Math.abs(this.y-b.y);
        }
    }
    
    public static void main(String[] args){
        int nCases = IO.nextInt();
        TAXI instance = new TAXI();
        instance.init(400+200+2, 2*(400+200+400*200));
        while(nCases-->0){
            instance.clear();
            int a, b, c, d;
            a = IO.nextInt();
            b = IO.nextInt();
            c = IO.nextInt();
            d = IO.nextInt();
            int sourceI = 0, sinkI = a+b+1;
            Point[] persons = new Point[a];
            Point[] taxis = new Point[b];
            
            for(int i=0;i<a;++i){
                int x, y;
                x = IO.nextInt();
                y = IO.nextInt();
                persons[i] = new Point(x, y);
                instance.addEdge(sourceI, i+1, 1);
            }
            
            int maxSteps = (c*d)/200;
            for(int i=0;i<b;++i){
                int x, y;
                x = IO.nextInt();
                y = IO.nextInt();
                taxis[i] = new Point(x, y);
                instance.addEdge(a+i+1, sinkI, 1);
                for(int i2=0;i2<persons.length;++i2){
                    int dist = taxis[i].distTo(persons[i2]);
                    if(dist<=maxSteps){
                        instance.addEdge(i2+1, a+i+1, 1);
                    }
                }
            }
            IO.println(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();
        }
    }
}

Maximum Bipartite Matching using Ford Fulkerson Algorithm (using DFS) - Java

Maximum Bipartite Matching is an application of the Ford Fulkerson Algorithm. 

1. Create a single source vertex for all vertices in one group-A.

2. Create a single sink vertex for all vertices in the other group-B.

3. Source vertex -> (group-A) vertices edges capacity = 1

4. (group-B) vertices -> sink edges capacity = 1

5. (group-A) vertices -> (group-B) edges capacity = 1

Example Graph used (Algorithms-Part II - coursera.com) -

Source:

import java.util.ArrayList;
import java.util.LinkedList;

public class MaximumBipartiteMatching {
    class Edge{
        int from, to;
        double capacity, flow;
        
        Edge(int f, int t, double capacity){
            from = f;
            to = t;
            this.capacity = capacity;
        }
        
        int other(int vertex){
            if(vertex==from)return to; else return from;
        }
        
        double capacity(){ return capacity; } 
        
        double flow(){ return flow; }
        
        double residualCapacityTo(int vertex){
            if(vertex==from)return flow; else return (capacity-flow);
        } 
        
        void increaseFlowTo(int vertex, double delta){
            if(vertex==from)flow = flow-delta;
            else flow = flow+delta;
        }
        
        @Override
        public String toString(){
            return from+" - "+to;
        }
    }
    
    ArrayList<ArrayList<Edge>> graph;
    private int V;
    private Edge[] edgeTo;
    private boolean[] marked;
    private double flow;
    
    MaximumBipartiteMatching(int V){
        this.V = V;
        graph = new ArrayList<>(V);
        for(int i=0;i<V;++i)graph.add(new ArrayList<>());
    }
    
    public void addEdge(int from, int to, double capacity){
        Edge e = new Edge(from, to, capacity); 
        graph.get(from).add(e);
        graph.get(to).add(e);
    }
    
    public void fordFulkerson(int s, int t){
        edgeTo = new Edge[V];
        while(augmentingPathExists(s, t)){ 
            double maxIncrease = 1; 
            
            System.out.print(" Matched Vertices -> "+(1+edgeTo[t].other(t))+" ");
            for(int i=t;i!=s;i=edgeTo[i].other(i)){ 
                if(edgeTo[i].other(i)==s)System.out.print((i+1)+"\n");
                maxIncrease = Math.min(maxIncrease, edgeTo[i].residualCapacityTo(i));
            }
            
            for(int i=t;i!=s;i=edgeTo[i].other(i)){ 
                edgeTo[i].increaseFlowTo(i, maxIncrease);
            } 
            flow+=maxIncrease;
        }
        System.out.println("Max flow = "+flow); 
    }
    
    public boolean augmentingPathExists(int s, int t){
        marked = new boolean[V]; 
        marked[s] = true; 
        quit = false;
        System.out.print("Augmenting Path : ");
        dfs(s, t);
        return marked[t];
    }
     
    boolean quit;
    public void dfs(int v, int sink){
        if(v==sink)quit = true;
        
        for(Edge e:graph.get(v)){
            if(quit)return;
                int other = e.other(v);
                if(!marked[other] && e.residualCapacityTo(other)>0){
                    System.out.print((1+other)+" ");  
                    edgeTo[other] = e;
                    marked[other] = true;  
                    dfs(other, sink);
                }
            }
    }
    
    public static void main(String[] args){
        int v = 10;
        MaximumBipartiteMatching m = new MaximumBipartiteMatching(v+2);
        int source = v, sink = v+1;
        m.addEdge(0,5,1);
        m.addEdge(0,6,1);
        m.addEdge(0,8,1);
        m.addEdge(1,5,1);
        m.addEdge(1,6,1);
        m.addEdge(2,5,1);
        m.addEdge(2,7,1);
        m.addEdge(2,8,1);
        m.addEdge(3,6,1);
        m.addEdge(3,9,1);
        m.addEdge(4,6,1);
        m.addEdge(4,9,1);
        
        for(int i=0;i<v/2;++i){ 
            m.addEdge(source, i, 1); 
            m.addEdge(v/2+i, sink, 1);
        }
        m.fordFulkerson(source, sink);
    }
}

Output:

Augmenting Path : 1 6 12  Matched Vertices -> 6 1

Augmenting Path : 2 6 1 7 12  Matched Vertices -> 7 2

Augmenting Path : 3 6 2 7 1 9 12  Matched Vertices -> 9 3

Augmenting Path : 4 7 2 6 3 8 12  Matched Vertices -> 8 4

Augmenting Path : 5 7 4 10 12  Matched Vertices -> 10 5

Augmenting Path : Max flow = 5.0