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:
"""
Dinic's Algorithm
最大フロー問題をO(VE^2)で解く
参考 : https://tjkendev.github.io/procon-library/python/max_flow/dinic.html

最大フローとはどんなものか
参考 : https://qiita.com/drken/items/e805e3f514acceb87602

Ford-Fulkerson Algorithm -> 最悪計算量がO(|f|(|V|+|E|))
DinicとEdmond-Karpが改良版としてある
どちらもO(VE^2)だけどDinicのほうが実用上早く動作することが多い。
違いはここに。
https://kopricky.github.io/code/NetworkFlow/dinic_memo.html

1. BFSで、sourceから各頂点までの距離(level)を計算する
2. DFSで、sourceからの距離が遠くなるようなパスを見つけフローを流す

DFSのキャパ更新方法(帰りがけ順)
参考 : https://qiita.com/drken/items/4a7869c5e304883f539b#3-4-dfs-%E3%81%AE%E6%8E%A2%E7%B4%A2%E9%A0%86%E5%BA%8F%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6%E3%81%AE%E8%A9%B3%E7%B4%B0
"""

from collections import deque
from collections import defaultdict
class Dinic:
    def __init__(self):
        # self.N = N
        self.G = defaultdict(list)
    
    def add_edge(self, fr, to, cap):
        """
        :param fr: 始点
        :param to: 終点
        :param cap: 容量
        """
        # forwardの最後には、キャパのうちどれだけ使ったかが入る
        forward = [to, cap, None]
        backward = [fr, 0, forward]
        forward[-1] = backward
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        """
        :param v1: 始点
        :param v2: 終点
        :param cap1: 容量1
        :param cap2: 容量2
        """
        edge1 = [v2, cap1, None]
        edge2 = [v1, cap2, edge1]
        edge1[-1] = edge2
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def bfs(self, s, t):
        """
        :param s: bfsの始点(source)
        :param t: bfsの終点(sink)
        :return: tに到達したかどうか。(sourceからの距離を保存しながら)
        """
        self.level = level = defaultdict(int)
        q = deque([s])
        level[s] = 1
        G = self.G
        while len(q) > 0:
            v = q.popleft()
            lv = level[v] + 1
            nexts = G[v]
            for w, cap, _ in nexts:
                if cap > 0 and level[w] == 0:
                    level[w] = lv
                    q.append(w)
        is_reach = (level[t] > 0)
        return is_reach

    def dfs(self, v, t, f):
        """
        :param v: 点v
        :param t: 終点(sink)
        :param f: v時点でのフロー
        :return: 終点到達時のフローを返す
        """   
        if v == t:
            return f
        level = self.level
        nexts = self.G[v]
        for edge in nexts:
            w, cap, rev = edge
            # まだキャパがあるならば
            if cap > 0 and level[v] < level[w]:
                # キャパが余ってるなら全部流すし
                # カツカツならキャパのmaxまで流す
                d = self.dfs(w, t, min(f, cap))
                # 帰りがけに、更新
                if d > 0:
                    # 順方向のキャパをd下げる
                    # 逆方向のキャパをd増やす
                    edge[1] -= d
                    rev[1] += d
                    return d
        # 次の道が見つからなければ終了
        return 0
    
    def flow(self, s, t):
        """
        :param s: 始点
        :param t: 終点
        :return : 最大フロー
        """
        flow = 0
        INF = 10**10
        G = self.G
        # ルートが存在する限り、続ける
        while self.bfs(s, t):
            f = INF
            while f > 0:
                f = self.dfs(s, t, INF)
                flow += f
        return flow

if __name__ == '__main__':
    """
    テストケースはここ
    http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A
    
    eg.
    4 5
    0 1 2
    0 2 1
    1 2 1
    1 3 1
    2 3 2

    ->3
    """
    N, M  = map(int, input().split())
    dinic = Dinic()
    for i in range(M):
        u, v, cap = map(int, input().split())
        dinic.add_edge(u, v, cap)
    s = 0
    t = N-1
    ans = dinic.flow(s,t)
    print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(200000)

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#DFSでの探索が済んでいるか否か
    
    def add_edge(self, fr, to, cap):#末尾はself.G[to]から対応する辺のself.G[fr]内でのindex
        self.G[fr].append([to,cap,len(self.G[to])])###{'to':to,"cap":cap,"rev";len(self.G[to})}みたいにしたほうがいいか
        self.G[to].append([fr,0,len(self.G[fr])-1])

    
    def bfs(self,s):#BFSで深さ決定,sがstart
        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:###capacity>0かつtoの深さ未定
                    self.level[e[0]] = self.level[v]+1
                    Q.append(e[0])

        
    def dfs(self,v,t,f):#DFSで増加パス探索,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 #cap減少
                    self.G[e[0]][e[2]][1] += d#逆辺のcap増加
                    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#DFSでの探索が済んでいるか否か
            f =self.dfs(s,t,self.inf)
            while f>0:
                flow+= f
                f = self.dfs(s,t,self.inf)
            
v,e = map(int, input().split( ))
D = Dinic(v)
for _ in range(e):
    u,w,c = map(int, input().split( ))
    D.add_edge(u,w,c)
ans = D.max_flow(0,v-1)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(200000)


def hierarchize(source: int) -> bool:
    global edges, hierarchy
    hierarchy = [-1] * n
    queue = deque([(0, source)])
    while queue:
        h, v = queue.popleft()
        if hierarchy[v] != -1:
            continue
        hierarchy[v] = h
        if v == sink:
            return True
        queue.extend((h + 1, target)
                     for remain, target, _ in edges[v]
                     if hierarchy[target] == -1 and remain)
    return False


def augment(v: int, limit: int) -> int:
    global sink, edges, hierarchy
    if v == sink:
        return limit
    res = 0
    for e in edges[v]:
        remain, target, idx = e
        if remain == 0 or hierarchy[v] >= hierarchy[target]:
            continue
        aug = augment(target, min(limit, remain))
        e[0] -= aug
        edges[target][idx][0] += aug
        res += aug
        limit -= aug
        if not limit:
            break
    return res


if __name__ == "__main__":
    n, m = map(lambda x: int(x), input().split())
    sink = n - 1
    edges = [[] for _ in range(n)]  # type: ignore

    hierarchy = [-1] * n

    for _ in range(m):
        s, t, c = map(lambda x: int(x), input().split())
        es, et = edges[s], edges[t]
        ls, lt = len(es), len(et)
        edges[s].append([c, t, lt])
        edges[t].append([0, s, ls])

    ans = 0
    while hierarchize(0):
        ans += augment(0, 10000001)

    print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
class Dinitz:
    #edge := (to, capa, rev_index)

    def __init__(self, N):
        self.__N = N
        self.__Graph = [[] for _ in range(N)] #to, capa, rev_index
        self.__level = [0] * N
        self.__iter = [0]*N

    def add_edge(self, from_, to, capa):
        self.__Graph[from_].append([to, capa, len(self.__Graph[to])])
        self.__Graph[to].append([from_, 0, len(self.__Graph[from_])-1 ])
    
    def solve(self, source:int, target:int):
        self.__target = target
        flow = 0
        while self.leveling_bfs(source):
            self.__iter = [0] * self.__N
            while True:
                delta = self.dfs(source, inf)
                if not delta:
                    break
                flow += delta
        return flow


    def leveling_bfs(self, source: int) -> bool:
        self.__level = [-1] * self.__N
        self.__level[source] = 0
        queue = deque([source])

        pop = queue.popleft
        append = queue.append
        while queue:
            from_ = pop()
            for to, capa, _ in self.__Graph[from_]:
                if capa > 0 > self.__level[to]:
                    self.__level[to] = self.__level[from_] + 1
                    append(to)
        return self.__level[self.__target] != -1 #到達可能ならTrue

    def dfs(self, from_:int,  flow:int) ->int:
        if from_ == self.__target:
            return flow
        for i in range(self.__iter[from_], len(self.__Graph[from_])):
            self.__iter[from_] = i
            to, capa, rev = edge = self.__Graph[from_][i]
            if capa and self.__level[from_] < self.__level[to]:
                delta = self.dfs(to, min(flow,capa))
                if delta: #増加パス
                    edge[1] -= delta #capaをへらす
                    self.__Graph[to][rev][1] += delta #逆辺のcapaを増やす
                    return delta
        return 0

def main():
    N,M = MI()
    dinic = Dinitz(N)
    for _ in range(M):
        a,b,c = MI()
        dinic.add_edge(a,b,c)
    ans = dinic.solve(0,N-1)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
class PushRelabel:
    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]
        self.initial = [N]*N
        self.zeros = [0]*(N+1)

    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)

    # Global labeling
    def bfs(self, H, D, t, que=deque()):
        que.append(t)
        G = self.G
        H[:] = self.initial
        H[t] = 0
        D[:] = self.zeros
        D[0] = 1
        c = N-1
        while que:
            v = que.popleft()
            d = H[v] + 1
            for w, cap, backward in G[v]:
                if H[w] <= d or backward[1] == 0:
                    continue
                H[w] = d
                D[d] += 1
                c -= 1
                que.append(w)
        D[N] = c
        return d # gap

    # FIFO preflow-push algorithm
    def flow(self, s, t):
        N = self.N
        H = [0]*N # height
        F = [0]*N # excess flow
        D = [0]*(N+1) # distance label
        active = [0]*N # active node

        G = self.G

        que = deque([s])
        F[s] = 10**18
        active[s] = 1

        gap = self.bfs(H, D, t)

        cnt = 0
        while que:
            v = que.popleft()
            if v == t:
                continue

            hv = H[v]
            # Gap-relabeling
            if hv > gap:
                D[hv] -= 1
                D[N] += 1
                hv = H[v] = N
                continue
            # push
            rest = F[v]
            for e in G[v]:
                w, cap, backward = e
                if cap and hv > H[w] < gap:
                    d = min(rest, cap)
                    e[1] -= d
                    backward[1] += d
                    rest -= d
                    F[w] += d
                    if not active[w]:
                        que.append(w)
                        active[w] = 1
                    if rest == 0:
                        break
            F[v] = rest

            if rest == 0:
                active[v] = 0
                continue

            # relabel
            h0 = H[v]
            hv = N
            for w, cap, backward in G[v]:
                if cap and hv > H[w] + 1 <= gap:
                    hv = H[w] + 1
            if hv != h0:
                D[h0] -= 1
                if D[h0] == 0 and h0 < gap:
                    gap = h0
                    hv = N
                elif hv == gap:
                    gap += 1
                D[hv] += 1

            H[v] = hv
            if hv < N:
                que.append(v)
            else:
                active[v] = 0

            cnt += 1
            if cnt % N == 0:
                gap = self.bfs(H, D, t)
        return F[t]

N, M = map(int, input().split())
pl = PushRelabel(N)
for i in range(M):
    u, v, c = map(int, input().split())
    pl.add_edge(u, v, c)
print(pl.flow(0, N-1))

Submission status: Accepted

Solution code:
import os
import sys
from collections import deque

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class Dinic:
    def __init__(self, graph=None, residual=None):
        """
        :param list of (list of (int, int)) graph: (to, cap) の隣接リスト
        :param list of (list of (list of (int|list))) residual: (to, cap, rev) の残余グラフ
        """
        assert (graph and not residual) or (not graph and residual)
        if graph:
            self.graph = self.residual_graph(graph)
        else:
            self.graph = residual

    @staticmethod
    def residual_graph(graph):
        """
        残余グラフ構築
        :param list of (list of (int, int)) graph: (to, cap) の隣接リスト
        :rtype: list of (list of (list of (int|list)))
        :return: (to, cap, rev) の残余グラフ
        """
        ret = [[] for _ in range(len(graph))]
        for v in range(len(graph)):
            for u, cap in graph[v]:
                rev = [v, 0]
                edge = [u, cap, rev]
                rev.append(edge)
                ret[v].append(edge)
                ret[u].append(rev)
        return ret

    def _dist(self, s):
        """
        :param int s:
        :rtype: list of int
        :return: s からの距離。残余グラフ上で到達できない場合は -1
        """
        ret = [-1] * len(self.graph)
        ret[s] = 0
        que = deque([(s, 0)])
        while que:
            v, d = que.popleft()
            for u, cap, _ in self.graph[v]:
                if ret[u] < 0 < cap:
                    ret[u] = d + 1
                    que.append((u, d + 1))
        return ret

    def _dfs(self, s, t, dist, iter, flow=float('inf')):
        """
        :param int s:
        :param int t:
        :param list of int dist:
        :param list of int iter:
        :param int flow:
        """
        if s == t:
            return flow
        while iter[s] < len(self.graph[s]):
            edge = self.graph[s][iter[s]]
            to, cap, rev = edge
            if dist[s] < dist[to] and cap > 0:
                f = self._dfs(to, t, dist, iter, min(flow, cap))
                if f > 0:
                    edge[1] -= f
                    rev[1] += f
                    return f
            iter[s] += 1
        return 0

    def maximum_flow(self, from_v, to_v):
        """
        :param int from_v:
        :param int to_v:
        :return: from_v から to_v への最大流
        """
        ret = 0
        while True:
            dist = self._dist(from_v)
            if dist[to_v] < 0:
                break
            iter = [0] * len(self.graph)
            while True:
                flow = self._dfs(from_v, to_v, dist, iter)
                if flow == 0:
                    break
                ret += flow
        return ret


V, E = list(map(int, sys.stdin.readline().split()))
UVC = [list(map(int, sys.stdin.readline().split())) for _ in range(E)]

graph = [[] for _ in range(V)]
for u, v, c in UVC:
    graph[u].append((v, c))
print(Dinic(graph=graph).maximum_flow(0, V - 1))

Submission status: Accepted

Solution code:
from collections import deque,defaultdict
import sys
def bfs(s,g,n):
    bfs_map = [-1]*n
    bfs_map[s] = 0
    q = deque([s])
    while q:
        x = q.popleft()
        for y in v[x]:
            if c[x][y] > 0 and bfs_map[y] < 0:
                bfs_map[y] = bfs_map[x]+1
                q.append(y)
    return bfs_map

def update(s,g,bfs_map):
    f = float("inf")
    p = [[None]*2 for i in range(bfs_map[g])]
    y = g
    for i in range(bfs_map[g])[::-1]:
        p[i][1] = y
        for x in v[y]:
            if c[x][y] > 0 and bfs_map[x] == i:
                if c[x][y] < f:
                    f = c[x][y]
                y = x
                p[i][0] = x
                break
        else:
            return 0

    for x,y in p:
        c[x][y] -= f
        c[y][x] += f
    return f

def dinic(s,g,n):
    f = 0
    while 1:
        bfs_map = bfs(s,g,n)
        if bfs_map[g] < 0:
            return f
        cap = update(s,g,bfs_map)
        while cap > 0:
            f += cap
            cap = update(s,g,bfs_map)
if __name__ == "__main__":
    n,e = map(int, sys.stdin.readline()[:-1].split())
    v = [[] for i in range(n)]
    c = [[0]*n for i in range(n)]
    for i in range(e):
        a,b,w = map(int,sys.stdin.readline()[:-1].split())
        v[a].append(b)
        v[b].append(a)
        c[a][b] = w
    print(dinic(0,n-1,n))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import deque

sys.setrecursionlimit(10 ** 9)
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()))
INF=float('inf')

class Dinic:
    def __init__(self, n):
        self.n = n
        self.links = [[] for _ in range(n)]
        self.depth = None
        self.progress = None
 
    def add_link(self, _from, to, cap):
        self.links[_from].append([cap, to, len(self.links[to])])
        self.links[to].append([0, _from, len(self.links[_from]) - 1])
 
    def bfs(self, s):
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        self.depth = depth
 
    def dfs(self, v, t, flow):
        if v == t:
            return flow
        links_v = self.links[v]
        for i in range(self.progress[v], len(links_v)):
            self.progress[v] = i
            cap, to, rev = link = links_v[i]
            if cap == 0 or self.depth[v] >= self.depth[to]:
                continue
            d = self.dfs(to, t, min(flow, cap))
            if d == 0:
                continue
            link[0] -= d
            self.links[to][rev][0] += d
            return d
        return 0
 
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.depth[t] < 0:
                return flow
            self.progress = [0] * self.n
            current_flow = self.dfs(s, t, float('inf'))
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, float('inf'))

N,M=MAP()
dinic=Dinic(N)
for i in range(M):
    u,v,c=MAP()
    dinic.add_link(u, v, c)

print(dinic.max_flow(0, N-1))

Submission status: Accepted

Solution code:
import collections


def bfs(u, n):
    global level, network
    level = [-1] * n
    deq = collections.deque()
    level[u] = 0
    deq.append(u)
    while deq:
        v = deq.popleft()
        for w, c, l in network[v]:
            if c > 0 and level[w] < 0:
                level[w] = level[v] + 1
                deq.append(w)


def dfs(u, t, f):
    global it, level, network
    if u == t:
        return f
    for i in range(it[u], len(network[u])):
        v, c, l = network[u][i]
        if c <= 0 or level[u] >= level[v]:
            continue
        d = dfs(v, t, min(f, c))
        if d <= 0:
            continue
        network[u][i][1] -= d
        network[v][l][1] += d
        it[u] = i
        return d
    it[u] = len(network[u])
    return 0


def max_flow(s, t, n):
    global it, level
    flow = 0
    while True:
        bfs(s, n)
        if level[t] < 0:
            return flow
        it = [0] * n
        while True:
            f = dfs(s, t, 1e10)
            if f > 0:
                flow += f
            else:
                break
    return flow


n, m = map(int, input().split())

network = [[] for _ in range(n)]
for _ in range(m):
    u, v, c = map(int, input().split())
    network[u].append([v, c, len(network[v])])
    network[v].append([u, 0, len(network[u]) - 1])

level = [-1] * n
it = [0] * n

print(max_flow(0, n - 1, n))

Submission status: Accepted

Solution code:
from collections import deque

class Edge:
    def __init__(self, fromNode, toNode, cap, rev=None):
        self.fromNode = fromNode
        self.toNode = toNode
        self.cap = cap
        self.rev = rev

class MaxFlow:
    def __init__(self, V):
        self.v = V
        self.edges = [[] for _ in range(V)]

    def addEdge(self, fromNode, toNode, cap):
        forEdge = Edge(fromNode, toNode, cap)
        backEdge = Edge(toNode, fromNode, 0)
        forEdge.rev = backEdge
        backEdge.rev = forEdge
        self.edges[fromNode].append(forEdge)
        self.edges[toNode].append(backEdge)
    
    def bfs(self, source, sink):
        self.level = [None] * self.v
        self.level[source] = 0
        que = deque()
        que.append(source)
        while que:
            node = que.popleft()
            newLevel = self.level[node] + 1
            for edge in self.edges[node]:
                if edge.cap and self.level[edge.toNode] is None:
                    self.level[edge.toNode] = newLevel
                    que.append(edge.toNode)

        return self.level[sink] is not None

    def dfs(self, node, sink, f):
        if node == sink: return f

        for edge in self.edges[node]:
            if edge.cap and self.level[edge.fromNode] < self.level[edge.toNode]:
                newFlow = self.dfs(edge.toNode, sink, min(f, edge.cap))
                if newFlow:
                    edge.cap -= newFlow
                    edge.rev.cap += newFlow
                    return newFlow

        return 0
    
    def run(self, source, sink):
        flow = 0
        INF = 10 ** 10
        while self.bfs(source, sink):
            addFlow = INF
            while addFlow:
                addFlow = self.dfs(source, sink, INF)
                flow += addFlow

        return flow

V, E = map(int, input().split())
net = MaxFlow(V)
for _ in range(E):
    u, v, c = map(int, input().split())
    net.addEdge(u, v, c)
print(net.run(0, V - 1))

Submission status: Accepted

Solution code:
from collections import deque
maxv,maxe = map(int ,input().split())
level = [0 for i in range(maxv)] #sからの距離
iter = [0 for i in range(maxv)] #どこまで調べ終わったか
edge = [[] for i in range(maxv)] #edge[i][ii] = (j,k,l) iから出るii番目の辺の終点がj,コストがk,逆辺はkから出る辺のうちl番目のやつ

for i in range(maxe):
    u,v,c = map(int ,input().split())
    edge[u].append((v,c,len(edge[v])))
    edge[v].append((u,0,len(edge[u])-1))

def bfs(s): #sからの最短距離
    global level
    level = [-1 for i in range(maxv)]
    q = deque([])
    q.append(s)
    level[s] = 0

    while len(q) > 0:
        vv = q.popleft()
        for ee in edge[vv]:
            if ee[1] > 0 and level[ee[0]] < 0:
                level[ee[0]] = level[vv]+1
                q.append(ee[0])

def dfs(v,t,f): #増加パスをdfsで探索
    global level,iter
    if v == t : return f
    for inde  in range(iter[v], len(edge[v])):
        ee = edge[v][inde]
        iter[v] = inde
        if (ee[1] > 0) and (level[v] < level[ee[0]]):
            d = dfs(ee[0],t,min(f,ee[1]))
            if d>0:
                lledge = list(edge[v][inde])
                lledge[1] -= d
                edge[v][inde] = tuple(lledge)
                ledge = list(edge[ee[0]][ee[2]])
                ledge[1] += d
                edge[ee[0]][ee[2]] = tuple(ledge)
                return d

    return 0

#sからtへのmaximal flowを求める
flow = 0
while True :
    bfs(0)
    if (level[maxv-1] < 0):
        break
    iter = [0 for i in range(maxv)]
    f =dfs(0,maxv-1,float('inf'))
    while f>0:
        flow += f
        f = dfs(0,maxv-1,float('inf'))

print(flow)

Submission status: Accepted

Solution code:
from collections import deque


class Dinic(object):
    __slots__ = ["inf", "v_count", "edges", "iter", "level"]

    def __init__(self, v_count: int, edges: list):
        self.inf = 10**9
        self.v_count = v_count
        self.edges = [[] for _ in [0]*v_count]
        self.iter = [0]*v_count
        self.level = None
        self._create_graph(edges)

    def _create_graph(self, _edges):
        edges = self.edges
        for origin, dest, cap in _edges:
            edges[origin].append([dest, cap, len(edges[dest])])
            edges[dest].append([origin, 0, len(edges[origin])-1])

    def solve(self, source: int, sink: int):
        max_flow = 0

        while True:
            self.bfs(source)
            if self.level[sink] < 0:
                return max_flow

            self.iter = [0]*self.v_count
            flow = self.dfs(source, sink, self.inf)

            while flow > 0:
                max_flow += flow
                flow = self.dfs(source, sink, self.inf)

    def bfs(self, source: int):
        level, edges = [-1]*self.v_count, self.edges
        level[source] = 0
        dq = deque([source])
        popleft, append = dq.popleft, dq.append

        while dq:
            v = popleft()
            for dest, cap, _rev in edges[v]:
                if cap > 0 > level[dest]:
                    level[dest] = level[v] + 1
                    append(dest)

        self.level = level

    def dfs(self, source: int, sink: int, flow: int) -> int:
        if source == sink:
            return flow
        while self.iter[source] < len(self.edges[source]):
            dest, cap, rev = edge = self.edges[source][self.iter[source]]
            if cap > 0 and self.level[source] < self.level[dest]:
                flowed = self.dfs(dest, sink, flow if flow < cap else cap)
                if flowed > 0:
                    edge[1] -= flowed
                    self.edges[dest][rev][1] += flowed
                    return flowed
            self.iter[source] += 1

        return 0


if __name__ == "__main__":
    import sys
    V, E = map(int, input().split())
    edges = []
    for a in (map(int, l.split()) for l in sys.stdin):
        edges.append(a)

    dinic = Dinic(V, edges)
    print(dinic.solve(0, V-1))

Submission status: Accepted

Solution code:
import sys
from collections import deque
parent=[]

def bfs(G,s,t,parent):
    N = len(G)
    visited=[False for u in range(N)]
    cola = deque()
    parent[s]=-1
    visited[s]=True
    cola.append(s)
    while cola:
        u = cola.popleft()
        for v in range(N):
            if(visited[v]==False and G[u][v]):
                cola.append(v)
                visited[v]=True
                parent[v]=u
    return visited[t]
    


def MAX_FLOW(G,s,t):
    global parent
    maxflow=0
    u,v=0,0
    GR=G
    while bfs(GR,s,t,parent):
        pathFlow=float("inf")
        v=t
        while v!=s:
            u=parent[v]
            pathFlow=min(pathFlow,GR[u][v])
            v=parent[v]
        v=t
        while v!=s:
          u=parent[v]
          GR[u][v]-=pathFlow
          GR[v][u]+=pathFlow
          v=parent[v]
        maxflow+=pathFlow
    return maxflow
        
        

def main():
    global parent
    D=[int(x) for x in sys.stdin.readline().strip().split()]
    V,E=D[0],D[1]
    G=[[0 for u in range(V)]for v in range(V)]
    for l in range(E):
        u,v,c= [int(x) for x in sys.stdin.readline().strip().split()]
        G[u][v]=c
    parent=[-1 for i in range(V)]
    print(MAX_FLOW(G,0,V-1))
main()