from collections import deque class mf_graph: n=0 g=[] def __init__(self,n_): self.n=n_ self.g=[[] for i in range(self.n)] self.pos=[] class _edge: to=0 rev=0 cap=0 def __init__(self,to_,rev_,cap_): self.to=to_ self.rev=rev_ self.cap=cap_ class edge: From=0 To=0 Cap=0 Flow=0 def __init__(self,from_,to_,cap_,flow_): self.From=from_ self.To=to_ self.Cap=cap_ self.Flow=flow_ def add_edge(self,From_,To_,Cap_): assert 0<=From_ and From_=0: continue level[e.to]=level[v]+1 if (e.to==t): return que.append(e.to) def dfs(v,up): if v==s:return up res=0 level_v=level[v] for i in range(Iter[v],len(self.g[v])): e=self.g[v][i] assert id(e)==id(self.g[v][i]) if level_v<=level[e.to] or self.g[e.to][e.rev].cap==0: continue d=dfs(e.to,min(up-res,self.g[e.to][e.rev].cap)) if d<=0:continue self.g[v][i].cap+=d self.g[e.to][e.rev].cap-=d res+=d if (res==up): return res level[v]=self.n return res flow=0 while(flow