## 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];

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) {
cap[edges] = capacity;
flow[edges] = 0;
prev[edges] = top[u];
top[u] = edges++;

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

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;

if (numChars == -1) {
throw new InputMismatchException();
}
if (curChar >= numChars) {
curChar = 0;
try {
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0) {
return -1;
}
}
return buf[curChar++];
}

public static int nextInt() {
while (isSpaceChar(c)) {
}
int sgn = 1;
if (c == '-') {
sgn = -1;
}
int res = 0;
do {
if (c < '0' || c > '9') {
throw new InputMismatchException();
}
res *= 10;
res += c - '0';
} while (!isSpaceChar(c));
return res * sgn;
}

public static char nextChar() {
while (isSpaceChar(c)) {
}
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();
}
}
}```