minimum cost flow - procom @ ウィキ

• 辺クラス

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

• 最小費用流(Bellman-Ford)

  final int INF = Integer.MAX_VALUE/2;
  List<Edge>[] list;
  int[] d;
  int[] prevv, preve;
   
  void addEdge(int from, int to, int cap, int cost) {
  	list[from].add(new Edge(to, cap, cost,list[to].size()));
  	list[to].add(new Edge(from, 0, -cost, list[from].size()-1));
  }
   
  int min_cost_flow(int s, int t , int f) {
  	int n = list.length;
  	d = new int[n];
  	prevv = new int[n]; preve = new int[n];
  	int res = 0;
  	while (f > 0) {
  		Arrays.fill(d, INF);
  		d[s] = 0;
  		boolean update = true;
  		while (update) {
  			update = false;
  			for (int v = 0; v < n; v++) {
  				if (d[v] == INF) continue;
  				for (int i = 0; i < list[v].size(); i++) {
  					Edge e = list[v].get(i);
  					if (e.cap > 0 && d[e.to] > d[v] + e.cost) {
  						d[e.to] = d[v] + e.cost;
  						prevv[e.to] = v;
  						preve[e.to] = i;
  						update = true;
  					}
  				}
  			}
  		}
   
  		if (d[t] == INF) return -1;
   
  		int c = f;
  		for (int v = t; v != s; v = prevv[v]) {
  			c = Math.min(c, list[prevv[v]].get(preve[v]).cap);
  		}
  		f -= c;
  		res += c * d[t];
  		for (int v = t; v != s; v = prevv[v]) {
  			Edge e = list[prevv[v]].get(preve[v]);
  			e.cap -= c;
  			list[v].get(e.rev).cap += c;
  		}
  	}
   
  	return res;
  }