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


import sys

file_input = sys.stdin

V, E = map(int, file_input.readline().split())

adj_mat = [[0] * V for i in range(V)]

for line in file_input:
    u, v, c = map(int, line.split())
    adj_mat[u][v] = c



import collections


def bfs(start, goal, parent):
    unvisited = [True] * V
    queue = collections.deque()
    queue.append(start)
    unvisited[start] = False
    while queue:
        u = queue.popleft()
        for v, r_capacity in enumerate(adj_mat[u]):
            if unvisited[v] and (r_capacity > 0):
                queue.append(v)
                unvisited[v] = False
                parent[v] = u
                if v == goal:
                    return not unvisited[goal]

def ford_fulkerson(source, sink):
    parent = [None] * V
    max_flow = 0
    while bfs(source, sink, parent):
        aug_path_flow = 10000
        v = sink
        while (v != source):
            aug_path_flow = min(aug_path_flow, adj_mat[parent[v]][v])
            v = parent[v]
        max_flow += aug_path_flow
        v = sink
        while (v != source):
            u = parent[v]
            adj_mat[u][v] -= aug_path_flow
            adj_mat[v][u] += aug_path_flow
            v = u
    return max_flow


print(ford_fulkerson(0, V - 1))

Solution (Python):


import sys

file_input = sys.stdin

V, E = map(int, file_input.readline().split())

adj_mat = [[0] * V for i in range(V)]

for line in file_input:
    u, v, c = map(int, line.split())
    adj_mat[u][v] = c



import collections


def bfs(start, goal, parent):
    level = [V] * V
    unvisited = [True] * V
    queue = collections.deque()
    queue.append(start)
    level[start] = 0
    unvisited[start] = False
    while queue:
        u = queue.popleft()
        next_level = level[u] + 1
        for v, r_capacity in enumerate(adj_mat[u]):
            if (level[v] >= next_level) and (r_capacity > 0):
                level[v] = next_level
                parent[v].append(u)
                if unvisited[v]:
                    queue.append(v)
                    unvisited[v] = False
    return level[goal]


def dfs(goal, path, parent, blocking_flow):
    v = path[-1]
    if v == goal:
        aug_path_flow = 10000
        for x, y in zip(path[1:], path[:-1]):
            aug_path_flow = min(aug_path_flow, adj_mat[x][y])
        for x, y in zip(path[1:], path[:-1]):
            adj_mat[x][y] -= aug_path_flow
            adj_mat[y][x] += aug_path_flow
        blocking_flow[0] += aug_path_flow
    else:
        for u in parent[v]:
            path.append(u)
            dfs(goal, path, parent, blocking_flow)
            path.pop()

def dinic(source, sink):
    max_flow = 0
    parent = [[] for i in range(V)]
    while bfs(source, sink, parent) != V:
        blocking_flow = [0]
        path = [sink]
        
        dfs(source, path, parent, blocking_flow)
        max_flow += blocking_flow[0]
        parent = [[] for i in range(V)]
    return max_flow


print(dinic(0, V - 1))

Solution (Python):
def bfs():
    visited = [False] * nv
    visited[0] = True
    q = [0]

    while q:
        u = q.pop(0)
        for i, w in enumerate(adj[u]):
            if not visited[i] and w > 0:
                q.append(i)
                visited[i] = True
                parents[i] = u

    return True if visited[nv - 1] else False

def maxf():
    max_flow = 0
    while bfs():
        flow = float('inf')
        c = nv - 1

        while c:
            flow = min(flow, adj[parents[c]][c])
            c = parents[c]

        max_flow += flow
        v = nv - 1

        while v:
            u = parents[v]
            adj[u][v] -= flow
            adj[v][u] += flow
            v = parents[v]

    return max_flow

nv, ne = map(int, input().split(' '))
adj = [[0] * nv for _ in range(nv)]
parents = [None] * nv

for _ in range(ne):
    s, t, w = map(int, input().split(' '))
    adj[s][t] = w

print(maxf())

Solution (Python):
class edge:
    def __init__(self,to,cap,rev):
        self.to,self.cap,self.rev=to,cap,rev

def makeG(n):
    return [[] for _ in xrange(n)]

def add(G,fr,to,cap):
    G[fr].append(edge(to,cap,len(G[to])))
    G[to].append(edge(fr,0,len(G[fr])-1))

def dfs(G,v,t,f,used):
    if v==t: return f
    used[v]=True
    for i in xrange(len(G[v])):
        e=G[v][i]
        if not used[e.to] and e.cap>0:
            d=dfs(G,e.to,t,min(f,e.cap),used)
            if d>0:
                e.cap-=d
                G[e.to][e.rev].cap+=d
                return d
    return 0
    
def max_flow(G,n,s,t):
    flow=0
    while True:
        used=[False]*n
        f=dfs(G,s,t,float("inf"),used)
        if f==0: return flow
        flow+=f

V,E=map(int,raw_input().split())
G=makeG(V)
for i in xrange(E):
    u,v,c=map(int,raw_input().split())
    add(G,u,v,c)
s=0
t=V-1
print(max_flow(G,V,s,t))

Solution (Python):
import collections
class Dinic:
    def __init__(self, n):
        self.n = n
        self.g = [[] for i in xrange(n)]
    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 add_multi_edge(self, v1, v2, cap1, cap2):
        self.g[v1].append([v2, cap1, len(self.g[v2])])
        self.g[v2].append([v1, cap2, len(self.g[v1])-1])
    def bfs(self, s):
        level = [-1]*self.n
        deq = collections.deque()
        level[s] = 0
        deq.append(s)
        while deq:
            v = deq.popleft()
            for e in self.g[v]:
                if e[1]>0 and level[e[0]]<0:
                    level[e[0]] = level[v] + 1
                    deq.append(e[0])
        self.level = level
    def dfs(self, v, t, f):
        if v==t: return f
        es = self.g[v]
        level = self.level
        for i in xrange(self.it[v], len(self.g[v])):
            e = es[i]
            if e[1]>0 and level[v]<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
                    self.it[v] = i
                    return d
        self.it[v] = len(self.g[v])
        return 0
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t]<0: break
            self.it = [0]*self.n
            while True:
                f = self.dfs(s, t, 10**9+7)
                if f>0:
                    flow += f
                else:
                    break
        return flow
V, E = map(int, raw_input().split())
dinic = Dinic(V)
for i in xrange(E):
    u, v, c = map(int, raw_input().split())
    dinic.add_edge(u, v, c)
print dinic.max_flow(0, V-1)

Solution (Python):
def main():
    nvertices, nedges = map(int, input().split())
    edges = [[0 for i in range(nvertices)] for j in range(nvertices)]
    for i in range(nedges):
        u, v, c = map(int, input().split())
        edges[u][v] = c

    ans = 0
    while True:
        val = bfs(0, nvertices - 1, edges)
        if val is None:
            break
        f, path = val
        ans += f
        for i in range(1, len(path)):
            u, v = path[i - 1], path[i]
            edges[u][v] -= f
            edges[v][u] += f

    print(ans)


def bfs(s, t, edges):
    visited = [False] * len(edges)
    INF = float('inf')
    que = [(s, INF, [s])]
    while que:
        u, f, path = que.pop()
        visited[u] = True
        if u == t:
            return (f, path)

        for v in range(len(edges)):
            if visited[v]:
                continue
            if edges[u][v] == 0:
                continue
            p = path[:]
            p.append(v)
            que.insert(0, (v, min(f, edges[u][v]), p))

    return None


main()

Solution (Python):
def main():
    nvertices, nedges = map(int, input().split())
    edges = [[0 for i in range(nvertices)] for j in range(nvertices)]
    for i in range(nedges):
        u, v, c = map(int, input().split())
        edges[u][v] = c

    INF = float('inf')
    ans = 0
    while True:
        parents = bfs(0, nvertices - 1, edges)
        if parents is None:
            break
        parent, child = parents[nvertices - 1], nvertices - 1
        f = INF
        while parent != -1:
            f = min(f, edges[parent][child])
            parent, child = parents[parent], parent

        ans += f
        parent, child = parents[nvertices - 1], nvertices - 1
        while parent != -1:
            edges[parent][child] -= f
            edges[child][parent] += f
            parent, child = parents[parent], parent

    print(ans)


def bfs(s, t, edges):
    visited = [False] * len(edges)
    que = [s]
    parents = [-1] * len(edges)
    while que:
        u = que.pop(0)
        visited[u] = True
        if u == t:
            return parents

        for v in range(len(edges)):
            if not visited[v] and edges[u][v] > 0:
                parents[v] = u
                que.append(v)

    return None


main()

Solution (Python):
def main():
    nvertices, nedges = map(int, input().split())
    adj = [[0 for i in range(nvertices)] for j in range(nvertices)]
    for i in range(nedges):
        u, v, c = map(int, input().split())
        adj[u][v] = c

    INF = float('inf')
    ans = 0
    while True:
        parents = bfs(0, nvertices - 1, adj)
        if parents is None:
            break
        v = nvertices - 1
        f = INF
        while parents[v] != -1:
            f = min(f, adj[parents[v]][v])
            v = parents[v]

        ans += f
        v = nvertices - 1
        while parents[v] != -1:
            adj[parents[v]][v] -= f
            adj[v][parents[v]] += f
            v = parents[v]

    print(ans)


def bfs(s, t, adj):
    visited = [False] * len(adj)
    que = [s]
    parents = [-1] * len(adj)
    while que:
        u = que.pop(0)
        visited[u] = True
        if u == t:
            return parents

        for v in range(len(adj)):
            if not visited[v] and adj[u][v] > 0:
                parents[v] = u
                que.append(v)

    return None


main()

Solution (Python):
def main():
    nvertices, nedges = map(int, input().split())
    adj = [[0] * nvertices for j in range(nvertices)]
    for i in range(nedges):
        u, v, c = map(int, input().split())
        adj[u][v] = c

    INF = float('inf')
    ans = 0
    while True:
        parents = bfs(0, nvertices - 1, adj)
        if parents is None:
            break
        v = nvertices - 1
        f = INF
        while parents[v] != -1:
            f = min(f, adj[parents[v]][v])
            v = parents[v]

        ans += f
        v = nvertices - 1
        while v != 0:
            u = parents[v]
            adj[u][v] -= f
            adj[v][u] += f
            v = u

    print(ans)


def bfs(s, t, adj):
    nvertices = len(adj)
    visited = [False] * nvertices
    visited[0] = True
    que = [s]
    parents = [-1] * nvertices
    while que:
        u = que.pop(0)
        if u == t:
            return parents

        for v in range(len(adj)):
            if not visited[v] and adj[u][v] > 0:
                parents[v] = u
                visited[v] = True
                que.append(v)

    return None


main()

Solution (Python):
def main():
    nvertices, nedges = map(int, input().split())
    adj = [[0] * nvertices for i in range(nvertices)]
    for i in range(nedges):
        u, v, c = map(int, input().split())
        adj[u][v] = c

    ans = 0
    while True:
        parents = bfs(0, nvertices - 1, adj)
        if parents is None:
            break
        v = nvertices - 1
        flow = float('inf')
        while parents[v] != -1:
            u = parents[v]
            flow = min(flow, adj[u][v])
            v = u
        ans += flow
        v = nvertices - 1
        while parents[v] != -1:
            u = parents[v]
            adj[u][v] -= flow
            adj[v][u] += flow
            v = u

    print(ans)


def bfs(s, t, adj):
    nvertices = len(adj)
    visited = [False] * nvertices
    parents = [-1] * nvertices
    visited[s] = True
    que = [s]
    while que:
        u = que.pop(0)
        if u == t:
            return parents
        for v in range(nvertices):
            if not visited[v] and adj[u][v] > 0:
                visited[v] = True
                parents[v] = u
                que.append(v)

    return None


main()

Solution (Python):
def main():
    nvertices, nedges = map(int, input().split())
    adj = [[0] * nvertices for j in range(nvertices)]
    for i in range(nedges):
        u, v, c = map(int, input().split())
        adj[u][v] = c

    INF = float('inf')
    ans = 0
    while True:
        parents = bfs(0, nvertices - 1, adj)
        if parents is None:
            break
        v = nvertices - 1
        f = INF
        while parents[v] != -1:
            u = parents[v]
            f = min(f, adj[u][v])
            v = u

        ans += f
        v = nvertices - 1
        while parents[v] != -1:
            u = parents[v]
            adj[u][v] -= f
            adj[v][u] += f
            v = u

    print(ans)


def bfs(s, t, adj):
    nvertices = len(adj)
    visited = [False] * nvertices
    visited[s] = True
    que = [s]
    parents = [-1] * nvertices
    while que:
        u = que.pop(0)
        if u == t:
            return parents

        for v in range(nvertices):
            if not visited[v] and adj[u][v] > 0:
                parents[v] = u
                visited[v] = True
                que.append(v)

    return None


main()

Solution (Python):
from collections import defaultdict

def dfs(source, sink, flow, connect):
    if source == sink:
        return flow
    used[source] = 1
    for i, (target, cost, rev_i) in enumerate(connect[source]):
        if not used[target] and cost > 0:
            that_flow = dfs(target, sink, min(flow, cost), connect)
            if that_flow > 0:
                connect[source][i][1] -= that_flow
                connect[target][rev_i][1] += that_flow
                return that_flow
    return 0

v_num, e_num = (int(n) for n in input().split(" "))
connect = defaultdict(list)
for _ in range(e_num):
    s, t, cost = (int(n) for n in input().split(" "))
    connect[s].append([t, cost, len(connect[t])])
    connect[t].append([s, 0, len(connect[s]) - 1])

answer = 0
while True:
    used = [0 for n in range(v_num)]
    now_flow = dfs(0, v_num - 1, float("inf"), connect)
    if now_flow == 0:
        break
    answer += now_flow
print(answer)

Solution (Python):
from collections import defaultdict

def dfs(source, sink, flow, connect):
    if source == sink:
        return flow
    used[source] = 1
    for i, (target, cost, rev_i) in enumerate(connect[source]):
        if not used[target] and cost > 0:
            that_flow = dfs(target, sink, min(flow, cost), connect)
            if that_flow > 0:
                connect[source][i][1] -= that_flow
                connect[target][rev_i][1] += that_flow
                return that_flow
    return 0

v_num, e_num = (int(n) for n in input().split(" "))
connect = defaultdict(list)
for _ in range(e_num):
    s, t, cost = (int(n) for n in input().split(" "))
    connect[s].append([t, cost, len(connect[t])])
    connect[t].append([s, 0, len(connect[s]) - 1])

answer = 0
base_used = [0 for n in range(v_num)]
while True:
    used = base_used.copy()
    now_flow = dfs(0, v_num - 1, float("inf"), connect)
    if now_flow == 0:
        break
    answer += now_flow
print(answer)

Solution (Python):
from collections import deque


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



class Dinic:
    def __init__(self, num_of_node: int):
        assert num_of_node > 0

        self.graph = [list() for _ in range(num_of_node)]   
        self.level = [None] * num_of_node      
        self.ite = [None] * num_of_node       

    
    def add_edge(self, f: int, t: int, cap: int):
        self.graph[f].append(Edge(t, len(self.graph[t]), cap))
        self.graph[t].append(Edge(f, len(self.graph[f]) - 1, 0))

    
    def max_flow(self, s: int, t: int):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0:
                return flow

            self.ite = [0] * len(self.ite)
            while True:
                f = self.dfs(s, t, 10 ** 10)
                if f > 0:
                    flow += f
                else:
                    break

    
    def bfs(self, s: int):
        self.level = [-1] * len(self.level)
        que = deque()
        que.append(s)
        self.level[s] = 0
        while len(que):
            v = que.popleft()

            for i in range(len(self.graph[v])):
                e = self.graph[v][i]
                if e.cap > 0 and self.level[e.to] < 0:
                    self.level[e.to] = self.level[v] + 1
                    que.append(e.to)

    
    def dfs(self, v: int, t: int, f: int):
        if v == t:
            return f

        for i in range(0, len(self.graph[v])):
            e = self.graph[v][i]
            if e.cap > 0 and self.level[v] < self.level[e.to]:
                d = self.dfs(e.to, t, min(f, e.cap))
                if d > 0:
                    self.graph[v][i].cap -= d
                    self.graph[e.to][e.rev].cap += d
                    return d
            self.ite[v] = i
        return 0


def main():
    V, E = map(int, input().split())
    dinic = Dinic(V)
    for _ in range(E):
        u, v, c = map(int, input().split())
        dinic.add_edge(u, v, c)

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


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque


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


class Dinic:
    def __init__(self, num_of_node: int):
        assert num_of_node > 0

        self.graph = [list() for _ in range(num_of_node)]   
        self.level = [None] * num_of_node      
        self.ite = [None] * num_of_node       

    
    def add_edge(self, f: int, t: int, cap: int):
        self.graph[f].append(Edge(t, 0, cap, len(self.graph[t]), False))
        self.graph[t].append(Edge(f, cap, cap, len(self.graph[f]) - 1, True))

    
    def max_flow(self, s: int, t: int):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0:
                return flow

            self.ite = [0] * len(self.ite)
            while True:
                f = self.dfs(s, t, 10 ** 10)
                if f > 0:
                    flow += f
                else:
                    break

    
    def bfs(self, s: int):
        self.level = [-1] * len(self.level)
        que = deque()
        que.append(s)
        self.level[s] = 0
        while len(que):
            v = que.popleft()

            for i in range(len(self.graph[v])):
                e = self.graph[v][i]
                if e.cap - e.flow > 0 and self.level[e.to] < 0:
                    self.level[e.to] = self.level[v] + 1
                    que.append(e.to)

    
    def dfs(self, v: int, t: int, f: int):
        if v == t:
            return f

        for i in range(self.ite[v], len(self.graph[v])):
            e = self.graph[v][i]
            if e.cap - e.flow > 0 and self.level[v] < self.level[e.to]:
                d = self.dfs(e.to, t, min(f, e.cap - e.flow))
                if d > 0:
                    self.graph[v][i].flow += d
                    self.graph[e.to][e.rev].flow -= d
                    return d
            self.ite[v] = i
        return 0


def main():
    V, E = map(int, input().split())
    dinic = Dinic(V)
    for _ in range(E):
        u, v, c = map(int, input().split())
        dinic.add_edge(u, v, c)

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


if __name__ == '__main__':
    main()

Solution (Python):

"""
Network Flow - Maximum Flow
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A&lang=jp

"""
import sys
from sys import stdin
from collections import namedtuple
input = stdin.readline

edge = namedtuple('edge', ['to', 'cap', 'rev'])

def add_edge(G, f, t, c):
    G[f].append(edge(t, c, len(G[t])))
    G[t].append(edge(f, 0, len(G[f]) - 1))


def dfs(G, used, v, t, f):
    if v == t:
        return f
    used[v] = True
    for i in range(len(G[v])):
        e = G[v][i]
        if (not used[e.to]) and (e.cap > 0):
            d = dfs(G, used, e.to, t, min(f, e.cap))
            if d > 0:
                G[v][i] = edge(e.to, e.cap - d, e.rev)
                G[e.to][e.rev] = edge(G[e.to][e.rev].to, G[e.to][e.rev].cap + d, G[e.to][e.rev].rev)
                return d
    return 0


def max_flow(G, V,s, t):
    used = [False] * V
    flow = 0
    while True:
        for i in range(len(used)):
            used[i] = False
        f = dfs(G, used, s, t, float('inf'))
        if f == 0:
            return flow
        flow += f


def main(args):
    V, E = map(int, input().split())

    G = [[] for _ in range(V)]
    for _ in range(E):
        u, v, c = map(int, input().split())
        add_edge(G, u, v, c)

    ans = max_flow(G, V, 0, V - 1)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):

"""
Network Flow - Maximum Flow
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A&lang=jp

"""
import sys
from sys import stdin
from collections import namedtuple, deque
input = stdin.readline

edge = namedtuple('edge', ['to', 'cap', 'rev'])


def add_edge(G, f, t, c):
    G[f].append(edge(t, c, len(G[t])))
    G[t].append(edge(f, 0, len(G[f]) - 1))


def bfs(G, level, s):
    for i in range(len(level)):
        level[i] = -1
    que = deque()
    level[s] = 0
    que.append(s)
    while que:
        v = que.popleft()
        for e in G[v]:
            if e.cap > 0 and level[e.to] < 0:
                level[e.to] = level[v] + 1
                que.append(e.to)


def dfs(G, iter, level, v, t, f):
    if v == t:
        return f
    for i in range(iter[v], len(G[v])):
        e = G[v][i]
        if e.cap > 0 and level[v] < level[e.to]:
            d = dfs(G, iter, level, e.to, t, min(f, e.cap))
            if d > 0:
                G[v][i] = edge(e.to, e.cap - d, e.rev)
                G[e.to][e.rev] = edge(G[e.to][e.rev].to, G[e.to][e.rev].cap + d, G[e.to][e.rev].rev)
                return d
    return 0

def max_flow(G, V, s, t):
    level = [0] * V
    flow = 0
    while True:
        bfs(G, level, s)
        if level[t] < 0:
            return flow
        iter = [0] * V
        while True:
            f = dfs(G, iter, level, s, t, float('inf'))
            if f > 0:
                flow += f
            else:
                break


def main(args):
    V, E = map(int, input().split())

    G = [[] for _ in range(V)]
    for _ in range(E):
        u, v, c = map(int, input().split())
        add_edge(G, u, v, c)

    ans = max_flow(G, V, 0, V - 1)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)



class Flow():
    def __init__(self, e, N):
        self.E = e
        self.N = N

    def max_flow(self, s, t):
        r = 0
        e = self.E

        def f(c, cap):
            v = self.v
            v[c] = 1
            if c == t:
                return cap
            for i in range(self.N):
                if v[i] or e[c][i] <= 0:
                    continue
                cp = min(cap, e[c][i])
                k = f(i, cp)
                if k > 0:
                    e[c][i] -= k
                    e[i][c] += k
                    return k
            return 0

        while True:
            self.v = [None] * self.N
            fs = f(s, inf)
            if fs == 0:
                break
            r += fs

        return r

def main():
    n,m = LI()
    aa = [LI() for _ in range(m)]

    e = [[0] * n for _ in range(n)]
    for a,b,c in aa:
        e[a][b] = c

    fl = Flow(e, n)
    r = fl.max_flow(0, n-1)

    return r


print(main())

Solution (Python):
class Edge():
    def __init__(self, to, cap, rev=None):
        self.to = to
        self.cap = cap
        self.rev = rev

from collections import deque

class Dinic():
    def __init__(self, n):
        self.n = n
        self.inf = 10**18
        self.graph = [[] for _ in range(self.n)]

    def add(self, fr, to, cap):
        edge = Edge(to, cap)
        rev = Edge(fr, 0)
        edge.rev, rev.rev = rev, edge
        self.graph[fr].append(edge)
        self.graph[to].append(rev)

    def max_flow(self, source, sink):
        flow = 0
        while True:
            queue = deque([source])
            level = [None for _ in range(self.n)]
            level[source] = 0
            while queue:
                node = queue.popleft()
                for edge in self.graph[node]:
                    to = edge.to
                    if edge.cap and level[to] is None:
                        level[to] = level[node] + 1
                        queue.append(to)
            if level[sink] is None: break
            stack = [source]
            par = [None for _ in range(self.n)]
            par[source] = source
            cap = [self.inf for _ in range(self.n)]
            while stack:
                node = stack.pop()
                if node == sink:
                    break
                for edge in self.graph[node]:
                    to = edge.to
                    if edge.cap and level[node] < level[to]:
                        par[to] = node
                        cap[to] = min(edge.cap, cap[node])
                        stack.append(to)
            node = sink
            prev = par[sink]
            delta = cap[sink]
            while node != source:
                for edge in self.graph[prev]:
                    if edge.to == node:
                        edge.cap -= delta
                        edge.rev.cap += delta
                node = prev
                prev = par[node]
            flow += delta
        return flow

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

d = Dinic(N)

for _ in range(M):
    u, v, c = map(int, input().split())
    d.add(u, v, c)

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

Solution (Python):
from collections import defaultdict
from collections import deque
import sys
sys.setrecursionlimit(200000)

def Dinic_DFS(v,g,maxflow,lines,cost,level):
    if v == g:
        return maxflow

    realflow = 0
    tmp = [i for i in lines[v]]
    for nex in tmp:
        if level[nex] > level[v]:
            
            plusflow = Dinic_DFS(nex,g,min(maxflow , cost[v][nex]),lines,cost,level)
            cost[v][nex] -= plusflow
            if cost[v][nex] == 0:
                lines[v].remove(nex)
            if cost[nex][v] == 0:
                lines[nex].add(v)
            cost[nex][v] += plusflow
            
            realflow += plusflow
            maxflow -= plusflow

            if maxflow <= 0:
                return realflow

    return realflow

def Dinic(s,g,lines,cost):

    N = len(cost)
    ans = 0

    while True:

        
        q = deque([s])
        level = [float("inf")] * N
        level[s] = 0
        while q:
            now = q.popleft()
            for nex in lines[now]:

                if level[nex] > level[now] + 1:
                    level[nex] = level[now] + 1
                    q.append(nex)

        if level[g] == float("inf"):
            return ans

        
        delta_flow = Dinic_DFS(s,g,float("inf"),lines,cost,level)
        while delta_flow > 0:
            ans += delta_flow
            delta_flow = Dinic_DFS(s,g,float("inf"),lines,cost,level)




N,M = map(int,input().split())

lines = defaultdict(set)
cost = [ [0] * N for i in range(N) ]

for i in range(M):

    u,v,c = map(int,input().split())
    
    
    
    if c != 0:
        lines[u].add(v)
        cost[u][v] += c

print (Dinic(0,N-1,lines,cost))

Solution (Python):
from collections import deque


class Dinic:
    def __init__(self, n: int):
        self.n = n
        self.INF = 10 ** 9 + 7
        self.graph = [[] for _ in range(n)]

    def add_edge(self, _from: int, to: int, capacity: int):
        """辺の追加
        1. _fromからtoへ向かう容量capacityの辺をグラフに追加する。
        2. toから_fromへ向かう容量0の辺をグラフに追加する。
        """
        forward = [to, capacity, None]
        forward[2] = backward = [_from, 0, forward]
        self.graph[_from].append(forward)
        self.graph[to].append(backward)

    def bfs(self, s: int, t: int):
        """capacityが正の辺のみを通ってsからtに移動可能かどうかBFSで探索する。
        level: sからの最短路の長さ
        """
        self.level = [-1] * self.n
        q = deque([s])
        self.level[s] = 0
        while q:
            _from = q.popleft()
            for to, capacity, _ in self.graph[_from]:
                if capacity > 0 and self.level[to] < 0:
                    self.level[to] = self.level[_from] + 1
                    q.append(to)

    def dfs(self, _from: int, t: int, f: int) -> int:
        """流量が増加するパスをDFSで探索する。
        BFSによって作られた最短路に従ってfを更新する。
        """
        if _from == t:
            return f
        for edge in self.itr[_from]:
            to, capacity, reverse_edge = edge
            if capacity > 0 and self.level[_from] < self.level[to]:
                d = self.dfs(to, t, min(f, capacity))
                if d > 0:
                    edge[1] -= d
                    reverse_edge[1] += d
                    return d
        return 0

    def max_flow(self, s: int, t: int) -> int:
        """s-tパス上の最大流を求める。計算量: O(|E||V|^2)"""
        flow = 0
        while True:
            self.bfs(s, t)
            if self.level[t] < 0:
                break
            self.itr = list(map(iter, self.graph))
            f = self.dfs(s, t, self.INF)
            while f > 0:
                flow += f
                f = self.dfs(s, t, self.INF)
        return flow


n, m = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(m)]


dn = Dinic(n)
for edge in edges:
    dn.add_edge(*edge)

ans = dn.max_flow(0, n - 1)
print(ans)