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

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

Solution (Python):
import sys
from collections import deque
 
 
class MaxFlow:
    class Edge:
        def __init__(self, to, cap, rev):
            self.to, self.cap, self.rev = to, cap, rev

    def __init__(self, node_size, inf):
        self._node = node_size
        self._inf = inf
        self._level = [-1]*self._node
        self._iter = [0]*self._node
        self._graph = [[] for _ in range(self._node)]

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

    def bfs(self, start):
        self._level = [-1]*self._node
        que = deque()
        self._level[start] = 0
        que.append(start)
        while que:
            cur_vertex = que.popleft()
            for e in self._graph[cur_vertex]:
                if e.cap > 0 > self._level[e.to]:
                    self._level[e.to] = self._level[cur_vertex] + 1
                    que.append(e.to)

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

    def solve(self, source, sink):
        flow = 0
        while True:
            self.bfs(source)
            if self._level[sink] < 0:
                return flow
            self._iter = [0]*self._node
            while True:
                f = self.dfs(source, sink, self._inf)
                if f == 0:
                    break
                flow += f
 
if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().split())
    mf = MaxFlow(n, 10**10)
    for _ in range(m):
        u, v, c = map(int, sys.stdin.readline().split())
        mf.add_edge(u, v, c)
    print(mf.solve(0, n-1))

Solution (Python):
vs,e = map(int,input().split())
edges = [[0]*vs for j in range(vs)] 
for i in range(e):
  u,v,c = map(int,input().split())
  edges[u][v] = c                   



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


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

  ans += f
  v = vs - 1
  while parents[v] != -1:
    u = parents[v]
    edges[u][v] -=f     
    edges[v][u] +=f     
    v = u
print(ans)

Solution (Python):
from collections import defaultdict
def main():
    v, e = map(int, input().split())
    g = defaultdict(set)
    residual = [[0] * v for _ in range(v)]
    source, sink = 0, v - 1

    for _ in range(e):
        s, t, c = map(int, input().split())
        if 0 < c and s != sink and t != source:
            g[s] |= {t}
            g[t] |= {s}
            residual[s][t] = c

    while True:
        route, flow = search(g, residual, source, sink)
        if not route:
            break
        for s, t in zip(route, route[1:]):
            residual[s][t] -= flow
            residual[t][s] += flow

    print(sum(residual[sink][i] for i in g[sink]))

def search(g, residual, source, sink):
    dfs_stack = [(source, None, float('inf'))]
    route = [None]
    visited = set()
    while dfs_stack:
        u, prev, flow = dfs_stack.pop()
        while route[-1] != prev:
            route.pop()
        route.append(u)
        visited |= {u}
        if u == sink:
            return route[1:], flow
        for v in g[u]:
            if v not in visited and 0 < residual[u][v]:
                dfs_stack.append((v, u, min(residual[u][v], flow)))
    return [], 0

main()

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,E = inpl()
Start = 0
Goal = N-1
ans = 0

lines = defaultdict(set)
cost = [[0]*N for i in range(N)]
for i in range(E):
	a,b,c = inpl()
	if c != 0:
		lines[a].add(b)
		cost[a][b] += c

def Ford_Fulkerson(s):	
	global lines
	global cost
	global ans

	queue = deque()		
	queue.append([s,INF])
	ed = [True]*N	
	ed[s] = False
	root = [0 for i in range(N)]	
	root[s] = -1

	
	while queue:
		s,flow = queue.pop()
		for t in lines[s]:	
			if ed[t]:
				flow = min(cost[s][t],flow)	
				root[t] = s
				queue.append([t,flow])
				ed[t] = False
				if t == Goal: 
					ans += flow
					break
		else:
			continue
		break
	else:
		return False

	
	t = Goal
	s = root[t]
	while s != -1:

		
		cost[s][t] -= flow
		if cost[s][t] == 0:
			lines[s].remove(t)

		
		if cost[t][s] == 0:
			lines[t].add(s)
		cost[t][s] += flow

		t = s
		s = root[t]
		
	return True

while True:
	if Ford_Fulkerson(Start):
		continue
	else:
		break

print(ans)