max flow - procom @ ウィキ

• 辺クラス

  class Edge {
  	int to;
  	int cap;
  	int rev;
  	Edge(int to, int cost, int rev) {
  		this.to = to;
  		this.cap = cost;
  		this.rev = rev;
  	}
  }

• Ford-Fulkerson法(隣接リスト)

  final int INF = Integer.MAX_VALUE/2;
  List<Edge>[] list;
  boolean[] used;
   
  void addEdge(int from, int to, int cap) {
  	list[from].add(new Edge(to, cap,list[to].size()));
  	list[to].add(new Edge(from, 0, list[from].size()-1));
  }
   
  int dfs(int v, int t, int f) {
  	if (v == t) return f;
  	used[v] = true;
  	for (int i = 0; i < list[v].size(); i++) {
  		Edge e = list[v].get(i);
  		if (!used[e.to] && e.cap > 0) {
  			int d = dfs(e.to, t, Math.min(f, e.cap));
  			if (d > 0) {
  				e.cap -= d;
  				list[e.to].get(e.rev).cap += d;
  				return d;
  			}
  		}
  	}
  	return 0;
  }
   
  int ford_fulkerson(int s, int t) {
  	int flow = 0;
  	while (true) {
  		Arrays.fill(used, false);
  		int f = dfs(s, t, INF);
  		if (f == 0) return flow;
  		flow += f;
  	}
  }