フォードファルカーソン法
キーワード
概要
有向グラフ と各辺の非負の容量 と始点 と終点 からなるネットワーク において、 から への最大流を求めるアルゴリズム。
増大路アルゴリズムとも呼ばれる。
ネットワークとフロー に対して、残余ネットワーク を以下のように定義する。
- 各辺 に対して、 ならば、 から への容量 からフロー を引いた値を容量とする辺 を追加する。
- 各辺 に対して、 ならば、フロー を容量とする辺 を追加する。
- 全ての辺のフローを 0 に初期化する。
- フロー値 を 0 に初期化する。
- から へのパスが存在する限り、以下の操作を繰り返す。
- 残余ネットワークにおいて、 から へのパス(フロー追加路)を見つける。
- そのパスにおける最小容量 を求める。
- そのパスにおける各辺 に対して、 または とする。
- フロー値 とする。
フロー追加路の探索には深さ優先探索を用いることが多い。
計算量
辺の数を 、最大流を とすると、計算量は である。
応用例
- 2 部マッチング
- 最小カット
- 最小費用流
- 配送の最適化
- 通信ネットワークの最適化
実装
type Edge struct {
to, cap, rev int // to: 行き先, cap: 容量, rev: 逆辺のインデックス
}
func main() {
var n, m int
scanIntVariables(&n, &m)
G := make([][]Edge, n+1) // 残余グラフ
for i := 0; i < m; i++ {
var a, b, c int
scanIntVariables(&a, &b, &c)
G[a] = append(G[a], Edge{b, c, len(G[b])})
G[b] = append(G[b], Edge{a, 0, len(G[a]) - 1})
}
visited := make([]bool, n+1)
var dfs func(v, t, d int) int
dfs = func(v, t, f int) int {
if v == t {
return f
}
visited[v] = true
for i := 0; i < len(G[v]); i++ {
if G[v][i].cap == 0 {
continue
}
if visited[G[v][i].to] {
continue
}
del := dfs(G[v][i].to, t, min(f, G[v][i].cap)) // パスの最小容量
if del > 0 {
G[v][i].cap -= del
G[G[v][i].to][G[v][i].rev].cap += del
return del
}
}
return 0
}
ans := 0
for { // 増加路がなくなるまで繰り返す
visited = make([]bool, n+1)
d := dfs(1, n, math.MaxInt32)
if d == 0 {
break
}
ans += d
}
writeLine(ans)
}