Saturday, January 30, 2016

EN - SPOJ (DFS) Solution - JAVA

Algorithm:

1. Find any path form source to sink (DFS/BFS). It is given that a path exists.
2. Now from the beginning node of this path,

             remove the current node from graph (set it visited).
             check if the path still exists.
             If it doesn't, the removed vertex is what you want.
             else check the same for the next node in the path until
             sink.
   
 
Source:

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

public class EN2 {  
    int maxnodes, maxedges, src, dest, edges;
    int[] top, head, prev;
    boolean marked;
    
    public void init(int maxnodes, int maxedges){
        this.maxnodes = maxnodes;
        this.maxedges = maxedges;  
        head = new int[maxedges];
        prev = new int[maxedges]; 
        top = new int[maxnodes];
        clear();
    }
    
    public void clear(){ 
        Arrays.fill(top, -1);
        edges = 0;
    } 
    
    public void addEdge(int u, int v, int capacity){
        head[edges] = v; 
        prev[edges] = top[u];
        top[u] = edges++;  
    }
    
     
    boolean dfs(int u){ 
        if(rec[u])return false;
        rec[u] = true;
         
        boolean sig=false;
        for(int e=top[u]; e>=0;e = prev[e]){
            int v = head[e];   
            from[v] = u;
            if(v==dest){from[dest] = u;return true;}
            sig = (dfs(v)==true);  
            if(sig)return sig;
        } 
        return sig;
    }
    
    int checkNodes(int u, int s, int t){  
        if(u==s)return -1; 
        int r = checkNodes(from[u], s, t);
        if(r!=-1)return r;
        Arrays.fill(rec, false);
        rec[u] = true;
        if(!dfs(s))return u;else return -1;
    }
     
    static boolean rec[];
    static int from[]; 
    public static void main(String[] args){
        int nC = IO.nextInt(); 
        
        EN2 instance = new EN2(); 
        
        //Input contains cases when m>100011. So a large value for m.
        instance.init((30011), 999999*2);
        
        while(nC-->0){  
            instance.clear(); 
            
            int n = IO.nextInt()-1;  
            
            rec = new boolean[n+1]; 
            from = new int[n+1];
            
            Arrays.fill(from, -1);
            instance.src = 0;
            instance.dest = n;
            
            int m = IO.nextInt(); 
            for(int i=0;i<m;++i){
                int a = IO.nextInt()-1;
                int b = IO.nextInt()-1; 
                instance.addEdge(a, b, 1); 
            }
            instance.dfs(0);
            int ret = instance.checkNodes(n, 0, n);
            IO.println(ret==-1?(n+1):(ret+1)); 
        }
        
    }  
    
    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();
        }
    }
}

Friday, January 29, 2016

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();
        }
    }
}

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();
        }
    }
}

Thursday, January 28, 2016

MTOTALF SPOJ (Dinic's Algorithm - Maxflow) Solution JAVA

Algorithm : Dinic's Maxflow

Source:

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

public class MTOTALF {

    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++;
    }

    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;
                    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;
    }

    public static void main(String[] args) { 
        int n = IO.nextInt();
        
        MTOTALF instance = new MTOTALF();
        instance.init('z'-'A'+1, 700);
        
        
        while (n-- > 0) {
            char a = IO.nextChar(); 
            char b = IO.nextChar();
            int f = IO.nextInt();

            instance.addEdge(a - 'A', b - 'A', f);
        }
         
        IO.println(instance.maxFlow('A' - 'A', 'Z' - 'A')); 
    }

    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();
        }
    }
}

Wednesday, January 27, 2016

IM (Intergalactic Map) SPOJ (Dinic's Algorithm - Maxflow) Solution - JAVA

Algorithm:

1. Split every vertex into a Vstart and Vend vertex.
2. Add a directed edge from Vstart to Vend with cap 1.
3. Add a source vertex X. Connect it to planet N and planet C
    by directed edges of capacity 1. (Xend -> Nstart, Xend -> Cstart)
4. Every V-V edge must be connected from Vend of some vertex to Vstart
    of some other with capacity 1.
5. Run Dinic's algorithm on the graph to find the max flow from
    source X to sink planet T.
6. If flow is equal to 2 that means there is a path from  N to T
    and a separate path from C to T.
7. Which means there is a path N-T-C. Which is what we wanted to know.
    Print YES if flow==2, NO otherwise.  

Source:


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

/*
    1. Split every vertex into a Vstart and Vend vertex.
    2. Add a directed edge from Vstart to Vend with cap 1.
    3. Add a source vertex X. Connect it to planet N and planet C
       by directed edges of capacity 1.
    4. Every V-V edge must be connected from Vend of some vertex to Vstart
       of some other with capacity 1.
    5. Run Dinic's algorithm on the graph to find the max flow from
       source X to sink planet T.
    6. If flow is equal to 2 that means there is a path from  N to T
       and a separate path from C to T. 
    7. Which means there is a path N-T-C. Which is what we wanted to know.
       Print YES if flow==2, NO otherwise.    
*/

public class IM { 
    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++; 
    }
    
    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; 
                    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;
    } 
    
    public static void main(String[] args){
        int nC = IO.nextInt(); 
        
        IM instance = new IM(); 
        
        instance.init((30011+1)*2, 5*50011);
        
        while(nC-->0){ 
            instance.clear();
            int n = IO.nextInt();
            int m = IO.nextInt(); 
            /*
                    m should have been <=50011 as specified
                    by the setter, but it isn't. Add the line
                    written below to get a WA!. 
            
                    if(m>50011)System.out.println("Get a WA!");
                    That's why 5*50011 as the no. of edges above.
            */
            int N = 1, T = 2, C = 3;
            int max = (n+1)*2;
            for(int i=2;i<max;i+=2){
                instance.addEdge(i, i+1, 1);
            }
            
            instance.addEdge(1, b(C), 1);
            instance.addEdge(1, b(N), 1);
            
            for(int i=0;i<m;++i){
                int a = IO.nextInt();
                int b = IO.nextInt();
                
                //Test cases have incorrect vertex numbers as well.
                if(a>30011 || b>30011 || a<=0 || b <=0 ) continue;
                 
                
                instance.addEdge(e(a), b(b), 1);
                instance.addEdge(e(b), b(a), 1); 
            }
             
            
            int flow = instance.maxFlow(1, b(T)); 
            if(flow==2)System.out.println("YES");
            else System.out.println("NO");
        }
    } 
    private static int b(int v){
        return v*2;
    }
    private static int e(int v){
        return v*2+1;
    }
    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;
        }
    }
}

Tuesday, January 26, 2016

NETADMIN SPOJ (DINIC's Algorithm - Maxflow) solution - JAVA.

Algorithm:

1. Add a sink vertex.
2. Connect each house wishing to connect to the internet (Zi) with the sink with capacity 1
    - directed edge from Zi to sink.
3. For each street, add an undirected edge between the two nodes with capacity that we decide later on.
4. The maximum number of colors that will be necessary is at most the number of houses wanting
    to connect to the internet.
5. The minimum capacity in the graph (of undirected edges) that fills the capacity of directed edges (Zi to sink with cap = 1) is the minimum number of colors required.
6. Use binary search to find out this capacity. Reset graph every time a different capacity is set according to the binary search procedure. Then use Dinic's algorithm to find out the max flow. The max flow must be equal to size(Z) and the capacity of undirected edges should be minimum.


Implementation structure of the graph- 
   
    head[i] - i indexes the ith edges' information.
    the head of this ith edge is indicated by head[i] i. i.e. the "to" value in [from-to]
   
    capacity[i], flow[i] = the capacity and flow of the ith edge
   
    prev[i] = the value i is the index of an edge.
    prev[i] stores the previous(based on insertion order) edge's index i.e. the index
    number used to store information about some previous "outgoing" edge that we recorded
    for the concerned vertex (the vertex from where this edge is originating).
    prev[i] is 0 when no more outgoing edge remains unconsidered for this vertex.
    Every edge's index number i can be used in prev[i] to get index number of the
    previous outgoing edge for the vertex being considered until a -1 is encountered.
   
    top[i] = the index used to store the last "outgoing" edge's index for this vertex i.
    if x == top[i], then we can use prev[x] to get the index of the previous
    (insertion order) outgoing edge from this vertex. This can be done until prev[i]
    returns -1 indicating no more outgoing edges remain unconsidered from this vertex.
   
    work[i] = is a temporary array constructed as a copy of the top[] array after the
    bfs() is done - a level graph has been constructed. It is used during the dfs procedure.
    It ensures that one edge is seen only once during multiple dfs' for a level graph.
    (Remove the assignment in the for loop and you get a TLE)
   
    Q is an array used as a queue
   
Source:

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

public class NETADMIN {
    static final int INF = 0x7fffffff;
 
    /*
    Structure of the graph- 
    
    head[i] - i indexes the ith edges' information.
    the head of this ith edge is indicated by head[i] i. i.e. the "to" value in [from-to]
    
    capacity[i], flow[i] = the capacity and flow of the ith edge
    
    prev[i] = the value i is the index of an edge.
    prev[i] stores the previous(based on insertion order) edge's index i.e. the index
    number used to store information about some previous "outgoing" edge that we recorded
    for the concerned vertex (the vertex from where this edge is originating). 
    prev[i] is 0 when no more outgoing edge remains unconsidered for this vertex.
    Every edge's index number i can be used in prev[i] to get index number of the
    previous outgoing edge for the vertex being considered until a -1 is encountered.
    
    top[i] = the index used to store the last "outgoing" edge's index for this vertex i. 
    if x == top[i], then we can use prev[x] to get the index of the previous
    (insertion order) outgoing edge from this vertex. This can be done until prev[i] 
    returns -1 indicating no more outgoing edges remain unconsidered from this vertex.
    
    work[i] = is a temporary array constructed as a copy of the top[] array after the 
    bfs() is done - a level graph has been constructed. It is used during the dfs procedure.
    It ensures that one edge is seen only once during multiple dfs' for a level graph.
    (Remove the assignment in the for loop and you get a TLE)
    
    Q is an array used as a queue
    */
    int maxnodes, maxedges, src, dest, edges;
    int[] top, work, Q;
    int[] head, prev, flow, cap, dist;
    
    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++; 
    }
    
    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; 
                    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;
    }
    
    public static void main(String[] args){
        InputReader r = new InputReader(System.in);
        NETADMIN task = new NETADMIN();
        task.init(501, 501*501);
        int nCases = r.nextInt();
        
        while(nCases-->0){
            task.clear();
            int n = r.nextInt();
            int s = 0;
            int t = n;
            int m = r.nextInt();
            int k = r.nextInt();
            
            for(int i=0;i<k;++i){
                int u = r.nextInt()-1;
                task.addEdge(u, t, 1);
            }
            
            for(int i=0;i<m;++i){
                int u = r.nextInt() - 1;
                int v = r.nextInt() - 1;
                task.addEdge(u, v, 1);
                task.addEdge(v, u, 1);
            }
            
            int lo = -1;
            int hi = k;
            while(hi-lo>1){
                int mid = (lo+hi)>>1;
                for(int i =0;i<task.edges; i++){
                    task.flow[i] = 0; 
                    if(task.head[i] != t){
                        task.cap[i] = mid; 
                    }
                }
                int flow = task.maxFlow(s, t);
                if(flow == k )hi = mid;
                else lo = mid;
            }
            System.out.println(hi);
        }
        
        
    }
    
    private static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar, numChars;

        public InputReader(InputStream stream) {
                this.stream = stream;
        }

        private 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 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 char nextChar() {
                int c = read();
                while (isSpaceChar(c)) c = read();
                return (char) c;
        }

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