A68 - Maximum Flow - 競プロ

A68 - Maximum Flow

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_bp

提出

code: python

# 1 2 3 4 5 6

# --5--

# ------4------

# --4--

# -------7-----

# ------3-----

# --3--

# --5--

# なぜ 8 になるのか

解答

code: python

# 最大フロー用の辺の構造体

class maxflow_edge:

def __init__(self, to, cap, rev):

self.to = to

self.cap = cap

self.rev = rev

# 深さ優先探索

def dfs(pos, goal, F, G, used):

if pos == goal:

return F # ゴールに到着：フローを流せる！

# 探索する

usedpos = True

for e in Gpos:

# 容量が 1 以上でかつ、まだ訪問していない頂点にのみ行く

if e.cap > 0 and not usede.to:

flow = dfs(e.to, goal, min(F, e.cap), G, used)

# フローを流せる場合、残余グラフの容量を flow だけ増減させる

if flow >= 1:

e.cap -= flow

Ge.toe.rev.cap += flow

return flow

# すべての辺を探索しても見つからなかった…

return 0

# 頂点 s から頂点 t までの最大フローの総流量を返す（頂点数 N、辺のリスト edges）

def maxflow(N, s, t, edges):

# 初期状態の残余グラフを構築

# （ここは書籍とは少し異なる実装をしているため、8 行目は Ga に追加された後なので len(Ga) - 1 となっていることに注意）

G = list() for i in range(N + 1)

for a, b, c in edges:

Ga.append(maxflow_edge(b, c, len(Gb)))

Gb.append(maxflow_edge(a, 0, len(Ga) - 1))

INF = 10 ** 10

total_flow = 0

while True:

used = False * (N + 1)

F = dfs(s, t, INF, G, used)

if F > 0:

total_flow += F

else:

break # フローを流せなくなったら、操作終了

return total_flow

# 入力

N, M = map(int, input().split())

edges = list(map(int, input().split())) for i in range(M)

# 答えを求めて出力

answer = maxflow(N, 1, N, edges)

print(answer)