
%\noindent \textbf{Min-cut / Max Flow}
\subsection{Min-cut / Max Flow}

Problem: Given a graph with capacities along edges, what is the maximum
flow from a start node, $s$, to an end node, $t$?
%The Ford-Fulkerson algorithm
%will compute the maximum flow.
%
%$c (u,v) \ge 0$ defines the capacity
%from node $u$ to node $v$. 
For a flow graph, multiple edges from
$u$ to $v$ and from $v$ to $u$ can be
combined into one edge with positive capacity. 
%The algorithm shown below
%maintains flow $f (u, v)$ for each pair of nodes such that
%$f (u, v) \le c (u, v)$ and $f (u, v) = -f(v, u)$.  Initial $f (u, v) = 0$.
%The residual flow, $r (u, v)$ is the net capacity of a link after pushing
%flow through an edge.  $r (u,v) = c (u, v) - f (u, v)$.  Finally, when finished,
%the maximum flow is $F = \sum_{i=1} f (s, i)$ where
%the sum goes over all edges from $s$.  Algorithm:
%
%\begin{lstlisting}
%while exists path P from s to t such that
% all residual flows on P are positive
%   rf = min{ r(u,v) for each edge (u,v) in P}
%   for each edge (u,v) in P
%       f (u, v) = f (u,v) + rf
%       f (v, u) = f (v, u) - rf
%\end{lstlisting}
%
%\noindent Picking the path is not trivial. Use a BFS to find
%the shortest path.  example code

\lstset{language=C++}
\begin{lstlisting}
#include <vector>
#include <queue>
#include <iostream>
#include <string>
#include <climits>

using namespace std;

typedef vector<int> Vec;
typedef vector<Vec> VV;
VV C; // capacity
VV F; // flow
VV E; // adj. list

int min_cut(int n, int s, int t) {
  while(true) {
    Vec P(n, -1); // parent table
    // capcity of path to node
    Vec M(n, 0);
    P[s] = s;
    M[s] = INT_MAX;

    queue<int> q;
    q.push(s);
    while(!q.empty()) {
      int u = q.front(); q.pop();
      for(int i = 0; i < E[u].size(); ++i) {
        int v = E[u][i];
        int w = C[u][v] - F[u][v];
        if( w > 0 && P[v] == -1) {
          P[v] = u;
          M[v] = min(M[u], w);
          if(v != t) {
            q.push(v);
          } else {
            while(P[v] != v) {
              u = P[v];
              F[u][v] += M[t];
              F[v][u] -= M[t];
              v = u;
            }
            q = queue<int>();
            break;
          }
        }
      }
    }
    // No more augmenting flows
    if(P[t] == -1) {
      int rv = 0;
      for(int i = 0; i < n; ++i)
        rv += F[s][i];
      return rv;
    }
  }
}

int main() {
 int V, Edges, a, b, c;
 int source, sink;
 char type;
 string line;
 while(cin >> type && cin.good()) {
   if(type == 'c') {
     getline(cin,line);
     continue;
   } else if(type == 'p') {
     cin >> line; // "max"
     cin >> V >> Edges;
     F = VV(V);
     C = VV(V);
     E = VV(V);
     for(int i = 0; i< V; ++i) {
       F[i] = Vec(V, 0);
       C[i] = Vec(V, 0);
       E[i] = Vec();
     }
   } else if(type == 'a') {
     // Input goes from 1-n,
     cin >> a >> b >> c;
     --a; --b;
     C[a][b] = c;
     E[a].push_back(b);
     E[b].push_back(a);
   } else if(type == 'n') {
     char s_or_t;
     cin >> a >> s_or_t;
     // Input goes from 1-n,
     --a;
     if(s_or_t == 's') source = a;
     else sink = a;
   } else {
     getline(cin,line);
     continue;
   }
 }
 cout << min_cut(V, source, sink) << endl;
}
\end{lstlisting}
\normalsize

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "../ref-doc"
%%% End:
