Maximum flow. Edmonds-Karp algorithm in O(min( E^2*V, E*FLOW ))

import java.util.*;

public class MaxFlowEdmondsKarp {

  static class Edge {
    int s, t, rev, cap, f;

    public Edge(int s, int t, int rev, int cap) {
      this.s = s;
      this.t = t;
      this.rev = rev;
      this.cap = cap;
    }
  }

  public static List<Edge>[] createGraph(int nodes) {
    List<Edge>[] graph = new List[nodes];
    for (int i = 0; i < nodes; i++)
      graph[inew ArrayList<>();
    return graph;
  }

  public static void addEdge(List<Edge>[] graph, int s, int t, int cap) {
    graph[s].add(new Edge(s, t, graph[t].size(), cap));
    graph[t].add(new Edge(t, s, graph[s].size() 10));
  }

  public static int maxFlow(List<Edge>[] graph, int s, int t) {
    int flow = 0;
    int[] q = new int[graph.length];
    while (true) {
      int qt = 0;
      q[qt++= s;
      Edge[] pred = new Edge[graph.length];
      for (int qh = 0; qh < qt && pred[t== null; qh++) {
        int cur = q[qh];
        for (Edge e : graph[cur]) {
          if (pred[e.t== null && e.cap > e.f) {
            pred[e.t= e;
            q[qt++= e.t;
          }
        }
      }
      if (pred[t== null)
        break;
      int df = Integer.MAX_VALUE;
      for (int u = t; u != s; u = pred[u].s)
        df = Math.min(df, pred[u].cap - pred[u].f);
      for (int u = t; u != s; u = pred[u].s) {
        pred[u].f += df;
        graph[pred[u].t].get(pred[u].rev).f -= df;
      }
      flow += df;
    }
    return flow;
  }

  // Usage example
  public static void main(String[] args) {
    List<Edge>[] graph = createGraph(3);
    addEdge(graph, 013);
    addEdge(graph, 022);
    addEdge(graph, 122);
    System.out.println(== maxFlow(graph, 02));
  }
}
Comments