// Some code is from "Algorithms in Java, Third Edition,"
// by Robert Sedgewick, Addison-Wesley, 2003.

// Network flows by maximum capacity paths and Edmonds-Karp (BFS)

// Program 22.3

class NetworkMaxFlow
{
  private Network G;

  private int sumFlow=0;

  private int s, t;

  private int[] wt;

  private int[] ord;

  private Edge[] st;

  private int ST(int v) { return st[v].other(v); }

  private void augment(int s, int t)
  // Used by both versions of maxflow
  {
    int d = st[t].capRto(t);
    for (int v = ST(t); v != s; v = ST(v))
      if (st[v].capRto(v) < d) 
        d = st[v].capRto(v);
    st[t].addflowRto(t, d); 
    for (int v = ST(t); v != s; v = ST(v))     
      st[v].addflowRto(v, d);

    sumFlow+=d;
    if (G.V()<200000000)
    {
      System.out.format("%d: %d",d,t);
      for (int v = ST(t); v != s; v = ST(v))
        System.out.format("<-%d",v);
      System.out.format("<-%d\n",s);
    }
  }

  // Program 22.4
  private boolean pfs()
  {
    intPQi pQ = new intPQi(G.V(), wt);
    for (int v = 0; v < G.V(); v++) 
    {
      wt[v] = 0;
      st[v] = null;
      pQ.insert(v);
    }
    wt[s] = -Edge.M;
    pQ.lower(s);  
    while (!pQ.empty()) 
    {
      int v = pQ.getmin();
      wt[v] = -Edge.M; 
      if (v == t)
        break;  
      if (v != s && st[v] == null)
        break;  
      AdjList A = G.getAdjList(v);
      for (Edge e = A.beg(); !A.end(); e = A.nxt()) 
      {
        int w = e.other(v);
        int cap = e.capRto(w);
        int P = cap < -wt[v] ? cap : -wt[v];

        if (cap > 0 && -P < wt[w]) 
        {
          wt[w] = -P;
          pQ.lower(w);
          st[w] = e;
        }
      }
    }
    return st[t] != null;
  }

  int cnt;

  private void searchC(int vIn)
  // Loosely based on program 18.8 to do BFS
  // Vertices go in Q rather than edges
  {
    IntQueue Q = new IntQueue(G.V());
    Q.put(vIn);
    ord[vIn] = cnt++; 
    while (!Q.empty())
    {
      int v = Q.get();
      if (v == t)
        break;

      AdjList A = G.getAdjList(v);
      for (Edge e = A.beg(); !A.end(); e = A.nxt())
      {
        int w = e.other(v);
        int cap = e.capRto(w);

        if (ord[w]==(-1) && cap>0)
        {
          Q.put(w);
          ord[w] = cnt++;
          st[w] = e;
        }
      }
    }
  }

  private boolean GraphBFSedge()
  {
    cnt = 0;
    ord = new int[G.V()];
    st = new Edge[G.V()];
    for (int t = 0; t < G.V(); t++)
    {
      st[t] = null;
      ord[t] = -1;
    }
    searchC(s);
    return st[t] != null;
  }

  NetworkMaxFlow(Network G, int s, int t,boolean useMCP)  
  {
    this.G = G;
    this.s = s;
    this.t = t;
    st = new Edge[G.V()];
    if (useMCP)
    {
      System.out.format("Using maximum capacity paths\n");
      wt = new int[G.V()];
      while (pfs())
        augment(s, t);
    }
    else
    {
      System.out.format("Using Edmonds-Karp BFS\n");
      while (GraphBFSedge())
        augment(s, t);
    }

    System.out.format("Edge capacities/flows\n");
    for (int v=0; v<G.V(); v++)
    {
      AdjList A = G.getAdjList(v);
      for (Edge e = A.beg(); !A.end(); e = A.nxt())
        if (v==e.v())
          System.out.format("%d->%d %d/%d\n",v,e.other(v),e.cap(),e.flow());
    }
    System.out.format("Max flow is: %d\n",sumFlow);
    if (G.V()<20)
    {
      System.out.format("S side: %d",s);
      for (int i=0; i<G.V(); i++)
        if (i!=s && st[i]!=null)
          System.out.format(" %d",i);
      System.out.format("\nT side:");
      for (int i=0; i<G.V(); i++)
        if (i!=s && st[i]==null)
          System.out.format(" %d",i);
      System.out.format("\n");
    }
  }
}