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

math_risan15_q.py

from atcoder.maxflow import MFGraph

N = 7  # Node数(駅の数)
M = 12  # Edge数(路線の数)

g = MFGraph(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.flow(0, 6))
for i in range(M):
    print(g.get_edge(i))
print(g.min_cut(0))

実行結果

35 # 最大流量
Edge(src=0, dst=1, cap=12, flow=12) # 渋谷 -> 新宿 12
Edge(src=0, dst=2, cap=25, flow=23) # 渋谷 -> 表参道 23
Edge(src=2, dst=1, cap=3, flow=3) # 表参道 -> 新宿 3
Edge(src=1, dst=3, cap=25, flow=15) # 新宿 -> 御茶ノ水 15
Edge(src=2, dst=4, cap=18, flow=18) # 表参道 -> 霞が関 18
Edge(src=2, dst=5, cap=2, flow=2) # 表参道 -> 赤坂見附 2
Edge(src=5, dst=1, cap=3, flow=0) # 赤坂見附 -> 新宿 0
Edge(src=5, dst=3, cap=2, flow=2) # 赤坂見附 -> 御茶ノ水 2
Edge(src=4, dst=5, cap=2, flow=0) # 霞が関 -> 赤坂見附 0
Edge(src=4, dst=3, cap=8, flow=1) # 霞が関 -> 御茶ノ水 1
Edge(src=3, dst=6, cap=21, flow=18) # 御茶ノ水 -> 東京 18
Edge(src=4, dst=6, cap=17, flow=17) # 霞が関 -> 東京 17
[True, False, True, False, False, False, False] # 最小カット (渋谷と表参道)