最大流 蟻本読んだメモ

参考にした資料：

蟻本第2版 P188～P191
ネットワークフロー入門　http://hos.ac/slides/20150319_flow.pdf

最大流問題

• 始点Sから終点Tまで各辺の容量を超えることなく流すことが出来る最大の流量を求める。

定義

• 有向グラフ,頂点の集合,辺の集合

• 始点,終点

• 各辺

• 容量

• 実際に流れる流量

条件

• 各辺はを満たす

• を含まない頂点に対して,へ入ってくる流量とから出ていく流量が等しい。つまり、

実際に最大流を求めるイメージ(Ford-Fulkerson法)

• 　辺の容量(最大でも流せる流量)

• 　辺に実際に流れている流量

1. 初期状態

2．パス s - 1 - 2 - t に5流す

3．パス s - 1 - 3 - t に5流す

4. パス s - 2 - 1 - 3 - tに1流す(逆辺を通る)

残余グラフ

グラフの各辺に対して逆辺を追加したグラフ、

そのグラフ上のである,　である逆辺のみからなるグラフを残余グラフという。

残余グラフでは辺の容量の定義は以下の通りになる

• 辺の容量

• 逆辺の容量

残余グラフ上のパス(sからtまでの辺,逆辺を通る経路)を増加路(増加パス)という

先程のイメージ図3を残余グラフとして表すと下図のようになる
(この図場合、の逆辺も表示しているが、取り除く場合もあるらしい)

• なら流量をあと増やせる

• なら流量をあと減らせる

実装(Java)

蟻本の写経です

import java.util.ArrayList;
import java.util.Arrays;

static final int INF = (int)1e9 + 7;
ArrayList<Edge>[] G;
boolean[] used;

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

public void addEdge(int from,int to,int cap){
	G[from].add(new Edge(to,cap,G[to].size()));
	G[to].add(new Edge(from,0,G[from].size()-1));
}

public int dfs(int v,int t,int f){

	if(v == t)return f;

	used[v] = true;
	for(int i = 0;i < G[v].size();i++){

		Edge e = G[v].get(i);

		if(!used[e.to] && e.cap > 0){
			int d = dfs(e.to,t,Math.min(f, G[v].get(i).cap));
			if(d > 0){

				e.cap -= d;
				G[e.to].get(e.rev).cap += d;
				return d;
			}
		}

	}

	return 0;
}

public int max_flow(int s,int t){
	int flow = 0;
	for(;;){

		Arrays.fill(used, false);
		int f = dfs(s,t,INF);
		if(f == 0)return flow;
		flow += f;
	}
}