#MMA Contest 018 H #最大流(stack DFS) from collections import deque # 最大流 V: 頂点数 import sys; sys.setrecursionlimit(10**7) # 燃やす埋めるにも対応 class maxflow: # S → A → def __init__(self,V): # ↓ ↓ ↓ self.V=V # → B → G self.G=[[] for _ in range(V)] # で、Sが残す頂点とする。このとき、 # Aを切るならBも切る、は A→B(inf)でOK def add_edge(self,u,v,c): # self.G[u].append([v,c,len(self.G[v]) ]) # Gには [移動先の頂点, 容量, 逆辺の位置] self.G[v].append([u,0,len(self.G[u])-1]) # G[u][辺番号] でアクセス可。逆辺は容量0 # def BFS(self,s): # D=[-1]*self.V; D[s]=0; Q=deque([s]) # while Q: # now=Q.popleft() # for nxt,cap,_ in self.G[now]: # 容量が残っている辺のみを有効辺とする if cap>0 and D[nxt]<0: # D[nxt]=D[now]+1 # Q.append(nxt) # return D # def stackDFS(self,start,fin,total,removed,D):# この頂点以遠の最大流量を考える flow=0; Q=[(start,total,False)] # stack DFS: 再帰の代わりにstackを使う while Q: # v,tf,back=Q.pop() # removed[v]: 頂点vの削除した辺数 if v==fin: flow=tf; continue # ゴールした場合はmax flowを流す if back and flow: # 入りがけか出がけかは変数backで管理 nxt,_,rev=self.G[v][removed[v]] # self.G[v][removed[v]][1]-=flow # このDFSでゴールに到達した場合 self.G[nxt][rev][1]+=flow # 変数flowがTrueとなり、この流量を流す continue # if back: removed[v]+=1 # 逆にゴールできなかった場合は辺を削除 while removed[v]0 and D[v]