読者です 読者をやめる 読者になる 読者になる

tookunn’s diary

主に競技プログラミング関係

最大流 蟻本読んだメモ

参考にした資料:

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


最大流問題

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

定義

  • G = 有向グラフ,V =頂点の集合,E = 辺の集合
  • s = 始点,t = 終点
  • e = 各辺(e \in E)
  • c(e) = 容量
  • f(e) = 実際に流れる流量

条件

  • 各辺e0 \le f(e) \le c(e)を満たす
  • s,tを含まない頂点v (v \in V\setminus\{s,t\})に対して,vへ入ってくる流量とvから出ていく流量が等しい。つまり、\sum_{e = *v}^{}f(e) = \sum_{e = v*}^{}f(e)

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

  •  C =  辺の容量(最大でも流せる流量)
  •  F =  辺に実際に流れている流量
1. 初期状態

f:id:tookunn:20170207185511p:plain

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

f:id:tookunn:20170207190100p:plain

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

f:id:tookunn:20170207190233p:plain

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

f:id:tookunn:20170207190520p:plain

残余グラフ

グラフGの各辺eに対して逆辺rev(e)を追加したグラフ、

そのグラフ上のf(e) \lt c(e)であるe, f(rev(e)) \gt 0である逆辺rev(e)のみからなるグラフを残余グラフという。

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

  • 辺の容量u_f(e) = c(e) - f(e)
  • 逆辺の容量u_f(rev(e)) = f(e)

残余グラフ上のs-tパス(sからtまでf(e) \lt c(e),f(rev(e)) \gt 0の辺,逆辺を通る経路)を増加路(増加パス)という

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

f:id:tookunn:20170207215904p:plain

  • u_f(e) \lt c(e)なら流量をあとu_f(e)増やせる
  • u_f(rev(e)) \gt 0なら流量をあとu_f(rev(e))減らせる

実装(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;
	}
}