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

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

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

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