Saturday, January 16, 2016

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

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
}

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

public static Edge[] hasAugmentingPath(){
Edge[] path = new Edge[V];
Arrays.fill(path, null);

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){
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){
else return from;
}
int capacityTo(int v){
if(v==to)return (capacity-flow);
else return flow;
}
if(v==to)this.flow += flow;
else this.flow -= flow;
}
public String toString(){return "["+from+"-"+to+":"+flow+"/"+capacity+"]";}
}
static class IO {

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[] 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[] 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[] 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[] 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 {
return Integer.parseInt(in);
}

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

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

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

public static String nextString() throws IOException {
}

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

1 comment:

1. Why does this algorithm works? Would you please explain it a bit more?