うさぎでもわかる離散数学（グラフ理論）　第15羽　最大フロー・最小カットの求め方 | 工業大学生ももやまのうさぎ塾 https://www.momoyama-usagi.com/entry/math-risan15#i-7

math_risan15_q.py

from collections import deque


class Dinic:                    
    def __init__(self, max_v):
        self.n = max_v
        self.G = [[] for _ in range(self.n)]

    def add_edge(self, fr, to, cap):  # frからtoへ向かう容量capの辺を追加する
        self.G[fr].append([to, cap, len(self.G[to])])
        self.G[to].append([fr, 0, len(self.G[fr]) - 1])

    def bfs(self, s):  # sからの最短距離をBFSで計算する
        self.level = [-1 for _ in range(self.n)]  # sからの距離
        que = deque()
        self.level[s] = 0
        que.append(s)
        while que:
            v = que.popleft()
            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if e[1] > 0 and self.level[e[0]] < 0:
                    self.level[e[0]] = self.level[v] + 1
                    que.append(e[0])

    def dfs(self, v, t, f):  # 増加パスをDFSで探す
        if v == t:
            return f
        for i in range(self.iter[v], len(self.G[v])):
            self.iter[v] = i
            e = self.G[v][i]
            if e[1] > 0 and self.level[v] < self.level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d > 0:
                    e[1] -= d
                    self.G[e[0]][e[2]][1] += d
                    return d
        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0:
                return flow
            self.iter = [0 for _ in range(self.n)]  # どこまで調べ終わったか
            f = self.dfs(s, t, float("inf"))
            while f > 0:
                flow += f
                f = self.dfs(s, t, float("inf"))


N = 7
g = Dinic(N)
g.add_edge(0, 1, 12)  # (0)渋谷 -> (1)新宿   12
g.add_edge(0, 2, 25)  # (0)渋谷 -> (2)表参道 25
g.add_edge(2, 1, 3)  # (2)表参道 -> (1)新宿 3
g.add_edge(1, 3, 25)  # (1)新宿 -> (3)御茶ノ水 25
g.add_edge(2, 4, 18)  # (2)表参道 -> (4)霞が関 18
g.add_edge(2, 5, 2)  # (2)表参道 -> (5)赤坂見附 2
g.add_edge(5, 1, 3)  # (5)赤坂見附 -> (1)新宿 3
g.add_edge(5, 3, 2)  # (5)赤坂見附 -> (3)御茶ノ水 2
g.add_edge(4, 5, 2)  # (4)霞が関 -> (5)赤坂見附 2
g.add_edge(4, 3, 8)  # (4)霞が関 -> (3)御茶ノ水 8
g.add_edge(3, 6, 21)  # (3)御茶ノ水 -> (6)東京 21
g.add_edge(4, 6, 17)  # (4)霞が関 -> (6)東京 17

print(g.max_flow(0, 6))

実行結果

35