「minimum cost flow」の編集履歴（バックアップ）一覧はこちら

「minimum cost flow」(2013/11/22 (金) 23:24:55) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

-辺クラス
#highlight(java){{
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)
#highlight(java){{
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;
}
}}