Problem:
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|$ 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

Solution (Python):

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))

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):
import sys

def dfs(node, sink, f, used, Edge): 
    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(): 
    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 = 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()

Solution (Python):
"""
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
"""

from collections import deque
from collections import defaultdict
class Dinic:
    def __init__(self):
        
        self.G = defaultdict(list)
    
    def add_edge(self, fr, to, cap):
        """
        :param fr: 始点
        :param to: 終点
        :param cap: 容量
        """
        
        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]:
                
                
                d = self.dfs(w, t, min(f, cap))
                
                if d > 0:
                    
                    
                    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)

Solution (Python):
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
    
    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(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)

Solution (Python):
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)]  

    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)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log 
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:
    

    def __init__(self, N):
        self.__N = N
        self.__Graph = [[] for _ in range(N)] 
        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 

    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 
                    self.__Graph[to][rev][1] += delta 
                    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()

Solution (Python):
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)

    
    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 

    
    def flow(self, s, t):
        N = self.N
        H = [0]*N 
        F = [0]*N 
        D = [0]*(N+1) 
        active = [0]*N 

        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]
            
            if hv > gap:
                D[hv] -= 1
                D[N] += 1
                hv = H[v] = N
                continue
            
            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

            
            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))

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):


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))

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
from collections import deque
maxv,maxe = map(int ,input().split())
level = [0 for i in range(maxv)] 
iter = [0 for i in range(maxv)] 
edge = [[] for i in range(maxv)] 

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): 
    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): 
    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


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)