Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Maximum Flow

A flow network is a directed graph which has a $source$ and a $sink$. In a flow network, each edge $(u, v)$ has a capacity $c(u, v)$. Each edge receives a flow, but the amount of flow on the edge can not exceed the corresponding capacity. Find the maximum flow from the $source$ to the $sink$.

Input

A flow network is given in the following format.

$|V|\;|E|$

$u_0\;v_0\;c_0$

$u_1\;v_1\;c_1$

:

$u_{|E|-1}\;v_{|E|-1}\;c_{|E|-1}$

$|V|$, $|E|$ is the number of vertices and edges of the flow network respectively. The vertices in $G$ are named with the numbers 0, 1,..., $|V|-1$. The source is 0 and the sink is $|V|-1$.

$u_i$, $v_i$, $c_i$ represent $i$-th edge of the flow network.
A pair of $u_i$ and $v_i$ denotes that there is an edge from $u_i$ to $v_i$ and $c_i$ is the capacity of $i$-th edge.

Output

Print the maximum flow.

Constraints

 $2 \leq |V| \leq 100$
	

 $1 \leq |E| \leq 1000$
	

 $0 \leq c_i \leq 10000$
	

Sample Input 1

4 5
0 1 2
0 2 1
1 2 1
1 3 1
2 3 2

Sample Output 1

3



Sample input:
4 5
0 1 2
0 2 1
1 2 1
1 3 1
2 3 2


Sample output:
3

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
from collections import defaultdict
INF = 10**9

def dfs_for_Ford_Fulkerson(N,E,capacity,s,g,flowing):
    stack = [(s,INF)]
    root = [0]*N
    root[s] = -1
    V = [False]*N
    V[s] = True
    while stack:
        # print(stack)
        u, flow = stack.pop()
        # print(u, E[u])
        for v in E[u]:
            # print(v)
            # print(V[v])
            # print(v, not V[v], capacity[(u,v)]>0)
            if not V[v] and capacity[(u,v)] > 0:
                root[v] = u
                V[v] = True
                if v == g:
                    if capacity[(u,v)] < flow:
                        flow = capacity[(u,v)]
                    break
                stack.append((v, min(flow, capacity[(u,v)])))
        else:
            continue
        break
    else:
        return False
    ## 更新
    now = g
    while now != s:
        before = root[now]
        capacity[(before, now)] -= flow
        capacity[(now, before)] += flow
        now = before
    flowing[0] += flow
    # print(capacity, flow)
    return True

def Ford_Fulkerson(N,E,capacity, s, g):
    flowing = [0]
    while dfs_for_Ford_Fulkerson(N,E,capacity,s,g, flowing):
        pass
    return flowing[0]

def main():
    N, M = map( int, input().split())
    E = [[] for _ in range(N)]
    capacity = defaultdict( int)
    for i in range(M):
        u, v, c = map( int, input().split())
        E[u].append(v)
        capacity[(u,v)] = c
        E[v].append(u)

    print( Ford_Fulkerson(N,E,capacity,0,N-1))
        
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
#import numpy as np
import re
import math
from collections import defaultdict
from collections import deque
import collections
from fractions import Fraction
from queue import PriorityQueue
import itertools
from copy import deepcopy
import random
import time
import os
import sys
import datetime
from functools import lru_cache
from functools import reduce
readline=sys.stdin.readline
sys.setrecursionlimit(2000000)
alphabet="abcdefghijklmnopqrstuvwxyz"
numbers="0123456789"
mod=int(10**9+7)
inf=int(10**19)
class Edge():
    def __init__(self,x,y,val=1):
        self.x=x
        self.y=y
        self.val=val
class unionfind():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(n)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):
            self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def yn(b):
    if b:print("yes")
    else:print("no")
def Yn(b):
    if b:print("Yes")
    else:print("No")
def YN(b):
    if b:print("YES")
    else:print("NO")
def ispow(a,b):
    now=b
    while now<a:
        now*=b
    return now==a
def getbin(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def getfacs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod_>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def nextcomb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:return num
def getprimes(n):
    if n==0:return []
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    ret=[]
    for a in range(n+1):
        if(A[a]):ret.append(a)
    return ret
def isprime(num):
    if(num<=1):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(bbool,ret1,ret2):
    if bbool:return ret1
    else:return  ret2
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n):
    b = 2
    ret=defaultdict(int)
    while b * b <= n:
        while n % b == 0:
            n //= b
            ret[b]+=1
        b+=1
    if n > 1:ret[n]+=1
    return ret
def pm(x):
    return x//abs(x)
def inputintlist(): 
    return list(map(int,input().split()))
def istanchouzouka(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>=a:
            f=False
        prev=a
    return f
def istanchouhigensyou(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>a:
            f=False
        prev=a
    return f
def getallsum(A):
    s=sum(A)
    dp=defaultdict(int)
    dp[0]=1
    for a in range(0,len(A)):
        for b in range(s,-1,-1):
            if b-A[a]>=0:
                dp[b]+=dp[b-A[a]]
    return dp
def yuukoutomukou(edges):
    ret=deepcopy(edges)
    for edge in edges:
        if not edge.x==edge.y:
            ret.append(Edge(edge.y,edge.x,edge.val))
    return ret
def dijkstra(edges,V,start):
    mincost=[inf]*V
    G=[[] for a in range(V)]
    for edge in edges:
        G[edge.x].append([edge.val,edge.y])
    Q=PriorityQueue()
    Q.put([0,start])#[cost,x]
    while not Q.empty():
        nowcost,nowx=Q.get()
        if mincost[nowx]==inf:
            mincost[nowx]=nowcost
            for cost,y in G[nowx]:
                newcost=nowcost+cost
                Q.put([newcost,y])
    return mincost
def warshallfloyd(edges,V):
    mincost=[[inf for b in range(V)] for a in range(V)]
    for a in range(V):mincost[a][a]=0
    for edge in edges:
        mincost[edge.x][edge.y]=min(mincost[edge.x][edge.y],edge.val)#x→yが複数ある場合のためにmin()する
    for k in range(V):
        for s in range(V):
            for t in range(V):
                if mincost[s][k]==inf or mincost[k][t]==inf:continue
                mincost[s][t]=min(mincost[s][t],mincost[s][k]+mincost[k][t])
    return mincost
def bellemanford(edges,V,start):
    mincost=[inf]*V
    mincost[start]=0
    for _ in range(V):
        for edge in edges:
            if mincost[edge.x]==inf:continue
            mincost[edge.y]=min(mincost[edge.y],mincost[edge.x]+edge.val)
    return mincost
def ruisekiwa(A):
    ret=[0]*(len(A)+1)
    for a in range(len(A)):
        ret[a+1]=ret[a]+A[a]
    return ret
def getmd(x1,y1,x2,y2):
    return abs(x1-x2)+abs(y1-y2)

class fordfulkerson():
    def __init__(self,edges,V,s,t):
        self.V=V
        self.used=[False]*V
        self.G=[[] for a in range(V)]
        self.s=s
        self.t=t
        for edge in edges:
            self.G[edge.x].append({"x":edge.x,"y":edge.y,"cap":edge.val,"rev":len(self.G[edge.y])})
            self.G[edge.y].append({"x":edge.y,"y":edge.x,"cap":0,"rev":len(self.G[edge.x])-1})
    def dfs(self,v,t,f=inf):
        if v==t:return f
        self.used[v]=True
        for a in range(len(self.G[v])):
            x=self.G[v][a]["x"]
            y=self.G[v][a]["y"]
            cap=self.G[v][a]["cap"]
            rev=self.G[y][self.G[x][a]["rev"]]
            if self.used[y] or cap==0:continue
            f2=self.dfs(y,t,min(f,cap))
            if f2>0:
                self.G[v][a]["cap"]-=f2
                rev["cap"]+=f2
                return f2
        return 0
    def maxflow(self):
        flow=0
        while True:
            self.used=[False]*V
            zouka=self.dfs(self.s,self.t)
            if zouka==0:break
            flow+=zouka
        return flow

######################################################################################################
V,E=inputintlist()
edges=[]
for e in range(E):
    edges.append(Edge(*inputintlist()))
ff=fordfulkerson(edges,V,0,V-1)
print(ff.maxflow())

Submission status: Accepted

Solution code:
import sys,collections
sys.setrecursionlimit(10000)

INF = float("inf")

V,E = map(int,sys.stdin.readline().split())
uvc = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(E)) # multi line with multi param
#uvc = [[0,1,1],[0,2,3],[1,2,1],[2,3,2]]
G = {i:{} for i in range(V)}
mG = {i:{} for i in range(V)}
for u,v,c in uvc:
    G[u][v] = c
    G[v][u] = 0
    mG[u][v] = 0
    mG[v][u] = 0
#print(G)
def dfs(current,flow):
    #print(current)
    if current == V-1:
        return flow
    visited.add(current)
    if not G[current]:
        return 0
    for nex,nex_c in G[current].items():
        if not nex in visited and nex_c != 0:
            f = dfs(nex,min(flow,nex_c))
            if f != 0:
                #print(current,nex,nex_c,f)
                mG[current][nex] = mG[current][nex] + f
                G[current][nex] = G[current][nex] - f
                G[nex][current] = G[nex][current] + f
                return f
    return 0

visited = set()
while dfs(0,INF) != 0:
    visited = set()
    #print("mG:",mG)
    #print("G:",G)
    pass
print(sum(mG[0].values()))

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(1000000)
    # 行先、上限、逆辺

    def add_edge(From, to, cap):
        g[From][to] = cap
        g[to][-From-1] = 0

    def max_flow(s, t):
        def dfs(v, t, f):
            q.append(v)
            if v == t:
                return f
            used[v] += 1
            for i in range(len(gkey[v])):
                to = gkey[v][i]
                cap = g[v][to]
                if to < 0:
                    to2 = -to-1
                else:
                    to2 = to
                if used[to2] or cap == 0:
                    continue
                d = dfs(to2, t, min(f, cap))
                if d > 0:
                    g[v][to] -= d
                    if to < 0:
                        to = -to-1
                    else:
                        v = -v-1
                    g[to][v] += d
                    return d
            q.pop()
            return 0

        flow = 0
        while True:
            used = [0]*n
            q = []
            f = dfs(s, t, 10**100)
            if not q:
                return flow
            flow += f

    n, m = map(int, input().split())
    g = [dict() for _ in range(n)]
    abc = [list(map(int, input().split())) for _ in [0]*m]
    for a, b, c in abc:
        add_edge(a, b, c)
    gkey = [list(i.keys()) for i in g]
    print(max_flow(0, n-1))


main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class Dinic:
    def __init__(self,v, inf =10**10):
        self.v = v
        self.inf = inf
        self.G = [[] for _ in range(v)]
        self.level = [-1]*v
        self.ite = [0]*v
    def add_edge(self, 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):
        self.level = [-1]*self.v
        self.level[s] = 0
        Q = deque()
        Q.append(s)
        while Q:
            v = Q.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
                    Q.append(e[0])

    def dfs(self,v,t,f):
        if v==t:
            return f
        for i in range(self.ite[v],len(self.G[v])):
            self.ite[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.ite = [0]*self.v
            f =self.dfs(s,t,self.inf)
            while f>0:
                flow+= f
                f = self.dfs(s,t,self.inf)

V, E = MAP()
D = Dinic(V)
for _ in range(E):
	u, v, c = MAP()
	D.add_edge(u, v, c)
ans = D.max_flow(0, V-1)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5+100)
from collections import *

class FordFulkerson:
    def __init__(self, N, edges):
        self.N = N
        self.G = defaultdict(lambda : defaultdict(int))
        
        for s, t, cap in edges:
            self.G[s][t] = cap
        
    def dfs(self, v, t, f):
        if v==t:
            return f
        
        self.used[v] = True
        
        for nv, cap in self.G[v].items():
            if not self.used[nv] and self.G[v][nv]>0:
                d = self.dfs(nv, t, min(f, self.G[v][nv]))
                
                if d>0:
                    self.G[v][nv] -= d
                    self.G[nv][v] += d
                    
                    return d
        
        return 0
    
    def max_flow(self, s, t):
        flow = 0
        
        while True:
            self.used = [False]*self.N
            f = self.dfs(s, t, 10**18)
        
            if f==0:
                return flow
        
            flow += f

V, E = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(E)]
ff = FordFulkerson(V, edges)
print(ff.max_flow(0, V-1))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

#ネットワークフロー
#最大流,最小カット
import queue
class Dinic():
    #Dinic法,O(|E||V|**2) ※但し、実際にはもっと高速な動作

    def __init__(self, v, inf = 10**10):
        # v:頂点数
        # G:辺情報.各頂点に対し、[行き先,重み,(この辺を含めず)既に存在する行き先の辺数]
        # level:startからの距離(これはcapacityを考慮しない) bfsで毎回リセットされる
        # iter:各頂点について、どこまで調べ終わったかを記録する
        self.V = v
        self.inf = inf
        self.G = [[] for _ in range(v)]
        self.level = [0 for _ in range(v)]
        self.iter = [0 for _ in range(v)]

    def add_edge(self, from_, to, cap):
        # to: 行き先, cap: 容量, rev: 反対側の辺

        # 無向グラフの場合、G[to]の方のcapを0→capにする必要があるので注意.('rev'はそのままで良い)

        self.G[from_].append({'to':to, 'cap':cap, 'rev':len(self.G[to])})
        self.G[to].append({'to':from_, 'cap':0, 'rev':len(self.G[from_])-1})

        

    # sからの最短距離をbfsで計算
    def bfs(self, s):
        self.level = [-1 for _ in range(self.V)]
        self.level[s] = 0
        que = queue.Queue()
        que.put(s)
        while not que.empty():
            v = que.get()
            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if e['cap'] > 0 and self.level[e['to']] < 0:
                    self.level[e['to']] = self.level[v] + 1
                    que.put(e['to'])

    # 増加パスをdfsで探す
    def dfs(self, v, t, f):
        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['cap'] > 0 and self.level[v] < self.level[e['to']]:
                d = self.dfs(e['to'], t, min(f, e['cap'])) # d:流量
                if d > 0:
                    e['cap'] -= d #使用済みの分だけcapから引く
                    self.G[e['to']][e['rev']]['cap'] += d
                    return d

        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s) #levelの更新
            # bfsでtに到達不可なら終了
            if self.level[t] < 0 : return flow
            #イテレータの初期化(イテレータ：各頂点に対し、どこまで調べ終わったか)
            self.iter = [0 for _ in range(self.V)]
            f = self.dfs(s, t, self.inf) #f:そのパスの流量
            while f > 0:
                flow += f
                f = self.dfs(s,t, self.inf)

v,e = map(int,readline().split())
V = v
network = Dinic(V)
for i in range(e):
    u,v,c = map(int,readline().split())
    network.add_edge(u,v,c)

print(network.max_flow(0,V-1))

Submission status: Accepted

Solution code:
from collections import deque

class Dinic:
    def __init__(self, N):
        self.N = N
        self.E = [[] for _ in range(N)]
    
    def add_edge(self, init, end, capacity):
        '''
            e[0] = the head vertex of e,
            e[1] = current capacity of e,
            e[2] = the index of reverse edge of e.
        '''
        self.E[init].append([end, capacity, len(self.E[end])])
        self.E[end].append([init, 0, len(self.E[init]) - 1])
    
    def _exist_augpath(self, s, t):
        self.level = level = [-1] * self.N # the level (depth) of each vertex
        E = self.E
        q = deque([(s, 0)]) # (vertex, level)
        while q:
            v, lv = q.popleft()
            if level[v] < 0: # visited v for the first time
                level[v] = lv
                for u, cap, _ in E[v]:
                    if cap == 0 or level[u] >= 0: continue
                    q.append((u, lv + 1))
        return level[t] >= 0
    
    def _blocking_flow(self, s, t):
        aug_flow = 0
        finished = [False] * self.N
        parent = [-1] * self.N
        revs = [-1] * self.N
        bottleneck = -1; temp_flow = 0
        E, level = self.E, self.level
        stack = [(s, -1, float('inf'), -1, 0)] # (vertex, parent, flow, rev_idx, status)
        while stack:
            v, p, f, rev, st = stack.pop()
            if temp_flow and v != bottleneck: continue
            if st == 0 and not finished[v]:
                parent[v] = p; revs[v] = rev
                if temp_flow: # offset
                    f -= temp_flow; temp_flow = 0; bottleneck = -1
                if v == t: # an augment path is found
                    aug_flow += f
                    if p != -1: stack += [(v, p, f, rev, 3)]
                    continue
                n_children = 0
                for u, cap, rev_idx in E[v]:
                    if cap == 0 or finished[u] or level[u] != level[v] + 1: continue
                    if n_children == 0:
                        stack += [(v, p, 0, rev, 2), (u, v, min(f, cap), rev_idx, 0)]
                        n_children += 1
                    else:
                        stack += [(v, p, 0, rev, 1), (u, v, min(f, cap), rev_idx, 0)]
                        n_children += 1
                if n_children == 0: # v is a leaf
                    finished[v] = True
            elif st == 1: # now searching
                continue
            elif st == 2: # search finished
                finished[v] = True
            else: # edge update
                rev_e = E[v][rev]; e = E[p][rev_e[2]]
                e[1] -= f; rev_e[1] += f
                if e[1] == 0: bottleneck = p
                if parent[p] != -1: stack += [(p, parent[p], f, revs[p], 3)]
                else: temp_flow = f
        return aug_flow
    
    def max_flow(self, s, t):
        flow = 0
        exist_augpath, blocking_flow = self._exist_augpath, self._blocking_flow
        while True:
            if not exist_augpath(s, t): break # no augment path is found
            flow += blocking_flow(s, t)
        return flow

N, M = map(int, input().split())
di = Dinic(N)
for _ in range(M):
    u, v, c = map(int, input().split())
    di.add_edge(u, v, c)
print(di.max_flow(0, N-1))

Submission status: Accepted

Solution code:
from collections import deque

class Dinic:
    class Edge:
        def __init__(self,to,cap,rev):
            self.to = to
            self.cap = cap
            self.rev = rev

    def __init__(self,n,inf = 10**9+7):
        self.n = n
        self.inf = inf
        self.level = [-1]*n
        self.iter = [0]*n
        self.e = [[] for _ in range(n)]

    def add_edge(self, from_, to, cap):
        self.e[from_].append(self.Edge(to, cap, len(self.e[to])))
        self.e[to].append(self.Edge(from_, 0, len(self.e[from_])-1))

    def bfs(self, start):
        self.level = [-1]*self.n
        dq = deque()
        self.level[start] = 0
        dq.append(start)
        while dq:
            cur_vertex = dq.popleft()
            for edge in self.e[cur_vertex]:
                if edge.cap > 0 > self.level[edge.to]:
                    self.level[edge.to] = self.level[cur_vertex] + 1
                    dq.append(edge.to)

    def dfs(self, cur_vertex, end_vertex, flow):
        if cur_vertex == end_vertex:return flow
        while self.iter[cur_vertex] < len(self.e[cur_vertex]):
            edge = self.e[cur_vertex][self.iter[cur_vertex]]
            if edge.cap > 0 and self.level[cur_vertex] < self.level[edge.to]:
                flowed = self.dfs(edge.to, end_vertex, min(flow, edge.cap))
                if flowed > 0:
                    edge.cap -= flowed
                    self.e[edge.to][edge.rev].cap += flowed
                    return flowed
            self.iter[cur_vertex] += 1
        return 0

    def compute(self, source, sink):
        flow = 0
        while True:
            self.bfs(source)
            if self.level[sink] < 0:return flow
            self.iter = [0]*self.n
            while True:
                f = self.dfs(source, sink, self.inf)
                if f == 0:break
                flow += f

def main():
    v,e = map(int,input().split())
    MF = Dinic(v)
    for i in range(e):
        a,b,c = map(int,input().split())
        MF.add_edge(a,b,c)
    print(MF.compute(0,v-1))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# Dinic's algorithm
from collections import deque
class Dinic:
    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def bfs(self, s, t):
        self.level = level = [None]*self.N
        deq = deque([s])
        level[s] = 0
        G = self.G
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        return level[t] is not None

    def dfs(self, v, t, f):
        if v == t:
            return f
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        INF = 10**9 + 7
        G = self.G
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow

n,m = map(int, input().split())
dinic = Dinic(n)
for _ in range(m):
    v,u,c = map(int, input().split())
    dinic.add_edge(v,u,c)

print(dinic.flow(0, n-1))

Submission status: Accepted

Solution code:
from collections import deque


class Dinic:
	def __init__(self, N):
		self.N = N
		self.edges = [[] for _ in range(N)]
		self.level = None
		self.iter = None

	def add_edges(self, u, v, cap):
		self.edges[u].append([v, cap, len(self.edges[v])])
		self.edges[v].append([u, 0, len(self.edges[u]) - 1])

	def bfs(self, s):
		self.level = [-1] * self.N
		self.level[s] = 0
		q = deque([s])
		while q:
			cur = q.popleft()
			for nxt, cap, _ in self.edges[cur]:
				if cap > 0 > self.level[nxt]:
					self.level[nxt] = self.level[cur] + 1
					q.append(nxt)

	def dfs(self, s, flow):
		if s == self.end:
			return flow
		for i in range(self.iter[s], len(self.edges[s])):
			self.iter[s] = i
			to, cap, opp = self.edges[s][i]
			if cap > 0 and self.level[s] < self.level[to]:
				d = self.dfs(to, cap if cap < flow else flow)
				if d > 0:
					self.edges[s][i][1] -= d
					self.edges[to][opp][1] += d
					return d
		return 0

	def maximum_flow(self, source, end):
		self.end = end
		max_flow = 0
		INF = float('inf')
		while True:
			self.bfs(source)
			if self.level[end] < 0:
				return max_flow
			self.iter = [0] * self.N
			flow = self.dfs(source, INF)
			while flow:
				max_flow += flow
				flow = self.dfs(source, INF)


v, e, *L = map(int, open(0).read().split())
dinic = Dinic(v)
for s, t, c in zip(*[iter(L)] * 3):
	dinic.add_edges(s, t, c)
print(dinic.maximum_flow(0, v - 1))

Submission status: Accepted

Solution code:
from collections import deque


class Dinic:
    """
    1-indexed
    """

    def __init__(self, N):
        self.N = N
        self.edge = [[] for _ in range(N + 1)]
        self.level = [-1] * (N + 1)

    def add_edge(self, v_from, v_to, cap):
        self.edge[v_from].append([v_to, cap, len(self.edge[v_to])])
        self.edge[v_to].append([v_from, 0, len(self.edge[v_from]) - 1])

    def _BFS(self, s):
        """
        sからの最短距離をBFSで計算する  
        """
        level = [-1] * (self.N + 1)
        level[s] = 0
        que = deque([s])
        while que:
            s = que.popleft()
            for t, cap, _ in self.edge[s]:
                if cap > 0 and level[t] < 0:
                    level[t] = level[s] + 1
                    que.append(t)
        self.level = level[:]

    def _DFS(self, v, goal, f):
        """
        増加パスをDFSで探す
        """
        if v == goal:
            return f
        for i in range(self.iterate[v], len(self.edge[v])):
            self.iterate[v] = i
            to, cap, rev = self.edge[v][i]
            if cap > 0 and self.level[v] < self.level[to]:
                d = self._DFS(to, goal, min(cap, f))
                if d > 0:
                    self.edge[v][i][1] -= d
                    self.edge[to][rev][1] += d
                    return d
        return 0

    def get_maximumFlow(self, s, t):
        """
        s -> tの最大流を求める
        1-indexed
        """
        self.goal = t
        inf = 10**18
        flow = 0
        while True:
            self._BFS(s)
            if self.level[t] < 0:
                return flow
            self.iterate = [0] * (self.N + 1)
            while True:
                f = self._DFS(s, t, inf)
                if f <= 0:
                    break
                flow += f


if __name__ == "__main__":
    N, M = map(int, input().split())
    max_flow = Dinic(N)
    for _ in range(M):
        a, b, c = map(int, input().split())
        max_flow.add_edge(a, b, c)

    ans = max_flow.get_maximumFlow(0, N-1)
    print(ans)

Submission status: Accepted

Solution code:
import sys

def dfs(node, sink, f, used, Edge): #最大流量fを返す
    if node == sink: return f
    used[node] = True
    for i, e in enumerate(Edge[node]):
        nextnode, nextcap, edgeIndex = e
        if not used[nextnode] and nextcap > 0: #次の行先が未探索で容量がある場合
            d = dfs(nextnode, sink, min(f, nextcap), used, Edge) 
            if d > 0:
                Edge[node][i][1] -= d
                Edge[nextnode][edgeIndex][1] += d
                return d
    return 0

def MF(): #頂点数V、辺数Eのグラフの最大流を返す
    input = sys.stdin.readline
    V, E = map(int, input().split())
    Edge = [[] for _ in range(V)]
    edgeSize = [0] * V
    for _ in range(E): #frmからtへ容量capの辺の入力を受ける(0-index)
        frm, t, cap = map(int, input().split())
        Edge[frm].append([t, cap, edgeSize[t]])
        Edge[t].append([frm, 0, edgeSize[frm]])
        edgeSize[t] += 1
        edgeSize[frm] += 1

    maxFlow = 0
    while True:
        visited = [False for _ in range(V)]
        f = dfs(0, V - 1, 1000000000, visited, Edge)
        if f == 0: break
        maxFlow += f
    print(maxFlow)
    
    return 0

if __name__ == "__main__":
    MF()