Ford-Fulkerson 法

フローネットワークの最大流を求めるアルゴリズムとして知られるFord-Fulkerson法の実装を理解するのに苦労したので、できるだけ処理の過程がわかりやすいような実装を試みる。

問題

問題設定については以下を参照。
Aizu Online Judge GRL_6_A

実装

graph は辞書からなる配列であり、graph[x].keys()がxに隣接する点のリストで、graph[x][y]が辺(x,y)の容量を表す。

def maximum_flow(graph, start, goal):
    INF = 1 << 30
    n = len(graph)
    max_flow = 0
    while True:
        # find path
        visited = [0] * n
        stack = [start]
        last = [None] * n
        while stack:
            x = stack.pop()
            visited[x] = 1
            if x == goal:
                break
            for y in graph[x].keys():
                if visited[y] or graph[x][y] == 0:
                    continue
                stack.append(y)
                last[y] = x
        if x != goal:
            break
        # min capacity
        y = goal
        min_capacity = INF
        while last[y] is not None:
            x = last[y]
            min_capacity = min(min_capacity, graph[x][y])
            y = x
        # update graph
        y = goal
        while last[y] is not None:
            x = last[y]
            graph[x][y] -= min_capacity
            graph[y][x] += min_capacity
            y = x
        max_flow += min_capacity
    return max_flow

解説

Ford-Fulkerson法では、以下の手続きにより最大流を求める。

max_flow <- 0
while startからgoalへのパスが存在:
    パスを1つとり、含まれる辺の容量の最小値をmin_capacityとする
    for (x, y) in パス:
        graph[x][y] -= min_capacity
        graph[y][x] += min_capacity
    max_flow += min_capacity

有向グラフにおいて、startからgoalまでのパスが存在するかは深さ優先探索を使って判定できる。その際、どの点から来たかを表す情報を管理しておくことによって、経路を復元することができる。

提出コード

n, m = map(int, input().split())
graph = [{} for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = c
    graph[b][a] = 0
print(maximum_flow(graph, 0, n - 1))