ディニッツ法
キーワード
概要
最大流問題のアルゴリズムの一つ。
フォードファルカーソン法やエドモンズカープ法よりも高速である。
エドモンズカープ法と同様に、最短のパスを探索することで、最大流を求める。
エドモンズカープ法は、毎回最短のパスを探索するが、ディニッツ法では、一度レベルネットワーク( 最短路 DAG)を構築し、その上で最短のパスを探索したのち、ブロックフローをまとめて更新するという手法を取る。
計算量
だが、実際にはもっと早い。
最短経路 DAG 上の DFS は、順番に辿ると長さ 以下の最短パスが得られるため で、一度増加路を通ると、少なくとも一本の辺が飽和するので、DFS が 回呼ばれる。
最短経路長は、ブロックフローを更新するたびに、少なくとも 増加し、最大で まで増加するため、BFS が 回呼ばれる。
したがって、全体の計算量は となる。
応用例
実装
type Edge struct {
to, cap, rev int
}
func main() {
var n, m int
scanIntVariables(&n, &m)
G := make([][]*Edge, n+1)
L := make([]int, n+1)
C := make([]int, 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})
}
s := 1
t := n
bfs := func() {
for i := 0; i <= n; i++ {
L[i] = -1
}
que := queue.New[int]()
que.Push(s)
L[s] = 0
for !que.Empty() {
v := que.Pop()
for _, e := range G[v] {
if e.cap > 0 && L[e.to] == -1 {
L[e.to] = L[v] + 1
que.Push(e.to)
}
}
}
}
var dfs func(v, f int) int
dfs = func(v, f int) int {
if v == t {
return f
}
for _, e := range G[v] {
if e.cap > 0 && L[v] < L[e.to] {
d := dfs(e.to, min(f, e.cap))
if d > 0 {
e.cap -= d
G[e.to][e.rev].cap += d
return d
}
}
}
return 0
}
ans := 0
for {
bfs()
if L[t] == -1 {
break
}
for {
for i := 0; i <= n; i++ {
C[i] = 0
}
f := dfs(s, 1<<60)
if f == 0 {
break
}
ans += f
}
}
writeLine(ans)
}ライブラリ化したもの
func NewMaximumFlow(size int) *MaximumFlow {
return &MaximumFlow{
graph: make([][]*Edge, size+1),
level: make([]int, size+1),
capacity: make([]int, size+1),
size: size,
}
}
func (mf *MaximumFlow) AddEdge(from, to, cap int) {
mf.graph[from] = append(mf.graph[from], &Edge{to, cap, len(mf.graph[to])})
mf.graph[to] = append(mf.graph[to], &Edge{from, 0, len(mf.graph[from]) - 1})
}
func (mf *MaximumFlow) MaxFlow(s, t int) int {
bfs := func() {
for i := 0; i <= mf.size; i++ {
mf.level[i] = -1
}
que := queue.New[int]()
que.Push(s)
mf.level[s] = 0
for !que.Empty() {
v := que.Pop()
for _, e := range mf.graph[v] {
if e.cap > 0 && mf.level[e.to] == -1 {
mf.level[e.to] = mf.level[v] + 1
que.Push(e.to)
}
}
}
}
var dfs func(v, f int) int
dfs = func(v, f int) int {
if v == t {
return f
}
for _, e := range mf.graph[v] {
if e.cap > 0 && mf.level[v] < mf.level[e.to] {
d := dfs(e.to, min(f, e.cap))
if d > 0 {
e.cap -= d
mf.graph[e.to][e.rev].cap += d
return d
}
}
}
return 0
}
flow := 0
for {
bfs()
if mf.level[t] == -1 {
break
}
for {
for i := 0; i <= mf.size; i++ {
mf.capacity[i] = 0
}
f := dfs(s, 1<<60)
if f == 0 {
break
}
flow += f
}
}
return flow
}
func main() {
var n, m int
scanIntVariables(&n, &m)
mf := NewMaximumFlow(n + 1)
for i := 0; i < m; i++ {
var a, b, c int
scanIntVariables(&a, &b, &c)
mf.AddEdge(a, b, c)
}
writeLine(mf.MaxFlow(1, n))
}