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

「max flow」(2013/11/22 (金) 18:31:42) の最新版変更点

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

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

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