Problem:


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

Maximum Flow

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

Input

A flow network is given in the following format.

$|V|\;|E|$

$u_0\;v_0\;c_0$

$u_1\;v_1\;c_1$

:

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

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

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

Output

Print the maximum flow.

Constraints

 $2 \leq |V| \leq 100$
	

 $1 \leq |E| \leq 1000$
	

 $0 \leq c_i \leq 10000$
	

Sample Input 1

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

Sample Output 1

3



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


Sample output:
3

Submission status: Accepted

Solution code:
import sys
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))

Submission status: Accepted

Solution code:
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                   #隣接行列にコストを追加していく

# print('edges',edges)

def bfs(s,t,edges):
  vs = len(edges) #隣接行列の縦の長さ
  visited = [False]*vs #頂点はvs個
  visited[s] = True    #bfsの始点をtrueに
  que = [s]
  parents = [-1]*vs
  while que:
    u = que.pop(0)   #queの先頭から主人公を取り出す
    if u == t:       #主人公が終点なら親を返す
      return parents
    for v in range(vs): #頂点v分forを回す
      if not visited[v] and edges[u][v] >0: #未訪問かつ容量があれば
        parents[v] = u  #vの親に始主人公sを入れる
        visited[v] = True
        que.append(v)
  return None


inf = float('inf')
ans = 0
while True:
  parents = bfs(0,vs-1,edges) #bfsで親を探す
  # print('parents',parents)
  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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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):	#sからFord-Fulkerson
	global lines
	global cost
	global ans

	queue = deque()		#BFS用のdeque
	queue.append([s,INF])
	ed = [True]*N	#到達済み
	ed[s] = False
	root = [0 for i in range(N)]	#ルート
	root[s] = -1

	#BFS
	while queue:
		s,flow = queue.pop()
		for t in lines[s]:	#s->t
			if ed[t]:
				flow = min(cost[s][t],flow)	#flow = min(直前のflow,line容量)
				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:

		#s->tのコスト減少，ゼロになるなら辺を削除
		cost[s][t] -= flow
		if cost[s][t] == 0:
			lines[s].remove(t)

		#t->s(逆順)のコスト増加，元がゼロなら辺を作成
		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)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop


class Edge:
    __slots__ = ('src', 'dest', 'capacity', 'flow')

    def __init__(self, v, w, capacity):
        self.src = v
        self.dest = w
        self.capacity = capacity
        self.flow = 0

    def other(self, v):
        if v == self.src:
            return self.dest
        else:
            return self.src

    def residual_capacity(self, v):
        if v == self.src:
            return self.capacity - self.flow
        else:
            return self.flow

    def add_flow(self, v, f):
        if v == self.src:
            self.flow += f
        else:
            self.flow -= f


class Network:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, edge):
        self._edges[edge.src].append(edge)
        self._edges[edge.dest].append(edge)

    def adj(self, v):
        return self._edges[v]


def max_flow(network, s, t):
    def augment_path():
        marked = [False] * network.v
        edge_to = [None] * network.v
        heap = [(-10**6, s, 0, None)]
        while heap:
            cap, v, n, e = heappop(heap)
            edge_to[v] = e
            if v == t:
                return (-cap, edge_to)
            if not marked[v]:
                marked[v] = True
                for ne in network.adj(v):
                    n += 1
                    w = ne.other(v)
                    c = ne.residual_capacity(v)
                    if not marked[w] and c > 0:
                        heappush(heap, (max(-c, cap), w, n, ne))

        return (0, [])

    while True:
        cap, path = augment_path()
        if cap == 0:
            break
        v = t
        e = path[t]
        while e is not None:
            v = e.other(v)
            e.add_flow(v, cap)
            e = path[v]

    return sum(e.flow for e in network.adj(s) if e.src == s)


def run():
    v, e = [int(i) for i in input().split()]
    s, t = 0, v-1
    net = Network(v)

    for _ in range(e):
        v, w, c = [int(i) for i in input().split()]
        net.add(Edge(v, w, c))

    print(max_flow(net, s, t))


if __name__ == '__main__':
    run()

Submission status: Runtime Error

Solution code:
V, E = map(int, input().split())

# -*- coding: utf-8 -*-
import collections
import queue


class Dinic():
    def __init__(self, N):
        self.N = N
        self.edges = collections.defaultdict(list)
        self.level = [0] * N
        self.iter = [0] * N

    def add(self, u, v, c, directed=True):
        """
        0-indexedでなくてもよいことに注意
        u = from, v = to, c = cap
        directed = Trueなら、有向グラフである
        """
        if directed:
            self.edges[u].append([v, c, len(self.edges[v])])
            self.edges[v].append([u, c, len(self.edges[u])-1])
        else:  # TODO
            self.edges[u].append([v, c, len(self.edges[u])])

    def bfs(self, s):
        self.level = [-1] * self.N
        self.level[s] = 0
        que = queue.Queue()
        que.put(s)
        while not que.empty():
            v = que.get(a)
            for i in range(len(self.edges[v])):
                e = self.edges[v][i]
                if e[1] > 0 and self.level[e[0]] < 0:
                    self.level[e[0]] = self.level[v] + 1
                    que.put(e[0])

    def dfs(self, v, t, f):
        if v == t:
            return f
        for i in range(self.iter[v], len(self.edges[v])):
            self.iter[v] = i
            e = self.edges[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.edges[e[0]][e[2]][1] += d
                    return d
        return 0

    def maxFlow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0:
                return flow
            self.iter = [0] * (self.N)
            f = self.dfs(s, t, float('inf'))
            while f > 0:
                flow += f
                f = self.dfs(s, t, float('inf'))


graph = Dinic(V)

for i in range(E):
    u, v, c = map(int, input().split())
    graph.add(u, v, c)

print(graph.maxFlow(0, V-1))

Submission status: Runtime Error

Solution code:
#test
def ford_fulkerson(graph, source, sink):
    N = len(graph)
    def dfs(cur_node, visited):
        if cur_node == source:
            flag = True
            while flag:
                flag = False
                for next_node in xrange(N):
                    if graph[cur_node][next_node] <= 0:
                        continue
                    for r, v in dfs(next_node, visited):
                        flag = True                        
                        yield [cur_node]+r, v
        elif cur_node == sink:
            yield [[], float("inf")]
        else:
            for next_node in xrange(N):                
                if visited[next_node] or graph[cur_node][next_node] <= 0:
                    continue
                visited[next_node] = True
                for route, volume in dfs(next_node, visited):
                    v = graph[cur_node][next_node]
                    if v <= 0:
                        break
                    volume = min(v, volume)
                    yield [[cur_node]+route, min(v, volume)]
                visited[next_node] = False
    for route, v in dfs(source, [False]*N):
        for s, t in zip(route, route[1:]):
            graph[s][t] -= v
            graph[t][s] += v

def main():
    V, E = map(int, raw_input().split())
    source, sink = V, V+1
    graph = [[0] * (V+2) for _ in xrange(V+2)]
    for _ in xrange(E):
        u, v, c = map(int, raw_input().split())
        graph[u][v] = c
    graph[source][0] = sum(graph[0])
    graph[V-1][sink] = sum(zip(*graph)[V-1])
    ford_fulkerson(graph, source, sink)
    print graph[0][source]

if __name__ == "__main__":
    for _ in xrange(2):
        main()

Submission status: Runtime Error

Solution code:
def read_data():
    nV, nE = map(int, input().split())
    cf = [dict() for v in range(nV)]
    for e in range(nE):
        u, v, c = map(int, input().split())
        if u == t or v == s:
            continue
        C[u][v] = c
        C[v][u] = 0
    return C, nV, 0, nV - 1

def dinic(cf, nV, s, t):
    dist = get_distance(cf, s, t)
    while dist[t] > 0:
        df = dfs(dist, cf, s, t, float('inf'))
        while df:
            df = dfs(dist, cf, s, t, float('inf'))
        dist = get_distance(cf, s, t)
    return sum(cf[t].values())

def get_distance(cf, s, t):
    dist = [-1] * len(cf)
    dist[s] = 0
    frontiers = [s]
    while frontiers:
        new_frontiers = []
        for u in frontiers:
            for v, capacity in cf[u].items():
                if dist[v] == -1 and capacity > 0:
                    dist[v] = dist[u] + 1
                    new_frontiers.append(v)
        frontiers = new_frontiers
    return dist

def dfs(dist, cf, u, t, df):
    if u == t:
        return df
    for v, capacity in cf[u].items():
        if dist[v] > dist[u] and capacity > 0:
            new_df = dfs(dist, cf, v, t, min(df, capacity))
            if new_df > 0:
                cf[u][v] -= new_df
                cf[v][u] += new_df
                return new_df
    return 0

if __name__ == '__main__':
    C, nV, s, t = read_data()
    print(dinic(C, nV, s, t))

Submission status: Runtime Error

Solution code:
def read_data():
    nV, nE = map(int, input().split())
    C = [dict() for v in range(nV)]
    for e in range(nE):
        u, v, c = map(int, input().split())
        if u == t or v == s:
            continue
        C[u][v] = c
        C[v][u] = 0
    return C, nV, 0, nV - 1

def dinic(cf, nV, s, t):
    dist = get_distance(cf, s, t)
    while dist[t] > 0:
        df = dfs(dist, cf, s, t, float('inf'))
        while df:
            df = dfs(dist, cf, s, t, float('inf'))
        dist = get_distance(cf, s, t)
    return sum(cf[t].values())

def get_distance(cf, s, t):
    dist = [-1] * len(cf)
    dist[s] = 0
    frontiers = [s]
    while frontiers:
        new_frontiers = []
        for u in frontiers:
            for v, capacity in cf[u].items():
                if dist[v] == -1 and capacity > 0:
                    dist[v] = dist[u] + 1
                    new_frontiers.append(v)
        frontiers = new_frontiers
    return dist

def dfs(dist, cf, u, t, df):
    if u == t:
        return df
    for v, capacity in cf[u].items():
        if dist[v] > dist[u] and capacity > 0:
            new_df = dfs(dist, cf, v, t, min(df, capacity))
            if new_df > 0:
                cf[u][v] -= new_df
                cf[v][u] += new_df
                return new_df
    return 0

if __name__ == '__main__':
    C, nV, s, t = read_data()
    print(dinic(C, nV, s, t))

Submission status: Runtime Error

Solution code:
class FordFulkerson:
    """Ford-Fulkerson Algorithm: find max-flow
       complexity: O(FE) (F: max flow)
    """
    def __init__(self, V, E, source, sink):
        """ V: the number of vertexes
            E: adjacency list
            source: start point
            sink: goal point
        """
        self.V = V
        self.E = [[] for _ in range(V)]
        for fr in range(V):
            for to, cap in E[fr]:
                self.E[fr].append([to, cap, len(self.E[to])])
                self.E[to].append([fr, 0, len(self.E[fr])-1])
        self.maxflow = self.ford_fulkerson(source, sink)

    def ford_fulkerson(self, source, sink, INF=10**9):
        """find max-flow"""
        def dfs(vertex, sink, flow):
            """find augmenting path"""
            if vertex == sink:
                return flow
            used[vertex] = True
            for i, (to, cap, rev) in enumerate(self.E[vertex]):
                if not used[to] and cap > 0:
                    d = dfs(to, sink, min(flow, cap))
                    if d > 0:
                        self.E[vertex][i][1] -= d
                        self.E[to][rev][1] += d
                        return d
            return 0

        maxflow = 0
        while True:
            used = [False] * self.V
            flow = dfs(source, sink, INF)
            if flow == 0:
                return maxflow
            else:
                maxflow += flow

V, E = map(int, input().split())
edge = [[] for _ in range(E)]
for _ in range(E):
    u, v, cap = map(int, input().split())
    edge[u].append((v, cap))
print(FordFulkerson(V, edge, 0, V-1).maxflow)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(3000)
class FordFulkerson:
    """Ford-Fulkerson Algorithm: find max-flow
       complexity: O(FE) (F: max flow)
    """
    def __init__(self, V, E, source, sink):
        """ V: the number of vertexes
            E: adjacency list
            source: start point
            sink: goal point
        """
        self.V = V
        self.E = [[] for _ in range(V)]
        for fr in range(V):
            for to, cap in E[fr]:
                self.E[fr].append([to, cap, len(self.E[to])])
                self.E[to].append([fr, 0, len(self.E[fr])-1])
        self.maxflow = self.ford_fulkerson(source, sink)

    def ford_fulkerson(self, source, sink, INF=10**9):
        """find max-flow"""
        def dfs(vertex, sink, flow):
            """find augmenting path"""
            if vertex == sink:
                return flow
            used[vertex] = True
            for i, (to, cap, rev) in enumerate(self.E[vertex]):
                if not used[to] and cap > 0:
                    d = dfs(to, sink, min(flow, cap))
                    if d > 0:
                        self.E[vertex][i][1] -= d
                        self.E[to][rev][1] += d
                        return d
            return 0

        maxflow = 0
        while True:
            used = [False] * self.V
            flow = dfs(source, sink, INF)
            if flow == 0:
                return maxflow
            else:
                maxflow += flow

V, E = map(int, input().split())
edge = [[] for _ in range(E)]
for _ in range(E):
    u, v, cap = map(int, input().split())
    edge[u].append((v, cap))
print(FordFulkerson(V, edge, 0, V-1).maxflow)

Submission status: Runtime Error

Solution code:
from collections import deque
class Dinic:
    """Dinic Algorithm: find max-flow
       complexity: O(EV^2)
    """
    class edge:
        def __init__(self, to, cap, rev):
            self.to, self.cap, self.rev = to, cap, rev

    def __init__(self, V, E, source, sink):
        """ V: the number of vertexes
            E: adjacency list
            source: start point
            sink: goal point
        """
        self.V = V
        self.E = [[] for _ in range(V)]
        for fr in range(V):
            for to, cap in E[fr]:
                self.E[fr].append(self.edge(to, cap, len(self.E[to])))
                self.E[to].append(self.edge(fr, 0, len(self.E[fr])-1))
        self.maxflow = self.dinic(source, sink)

    def dinic(self, source, sink):
        """find max-flow"""
        INF = float('inf')
        maxflow = 0
        while True:
            self.bfs(source)
            if self.level[sink] < 0:
                return maxflow
            self.itr = [0] * self.V
            while True:
                flow = self.dfs(source, sink, INF)
                if flow > 0:
                    maxflow += flow
                else:
                    break            

    def dfs(self, vertex, sink, flow):
        """find augmenting path"""
        if vertex == sink:
            return flow
        for i in range(self.itr[v], len(self.E[vertex])):
            self.itr[v] = i
            e = self.E[vertex][i]
            if e.cap > 0 and self.level[vertex] < self.level[e.to]:
                d = self.dfs(e.to, sink, min(flow, e.cap))
                if d > 0:
                    self.E[vertex][i] -= d
                    self.E[e.to][e.rev].cap += d
                    return d
        return 0

    def bfs(self, start):
        """find shortest path from start"""
        que = deque()
        self.level = [-1] * self.V
        que.append(start)
        self.level[start] = 0
        
        while que:
            fr = que.popleft()
            for e in self.E[fr]:
                if e.cap > 0 and self.level[e.to] < 0:
                    self.level[e.to] = self.level[fr] + 1
                    que.append(e.to)        

V, E = map(int, input().split())
edge = [[] for _ in range(V)]
for _ in range(E):
    u, v, cap = map(int, input().split())
    edge[u].append((v, cap))
print(Dinic(V, edge, 0, V-1).maxflow)

Submission status: Runtime Error

Solution code:
from queue import deque


def hierarchize(source):
    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, limit):
    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


n, m = map(int, input().split())
sink = n - 1
edges = [[] for _ in range(n)]

hierarchy = [-1] * n

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

res = 0
while hierarchize(0):
    res += augment(0, 10000001)
print(res)

Submission status: Runtime Error

Solution code:
import sys
from queue import deque

sys.setrecursionlimit(200000)


def hierarchize(source):
    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, limit):
    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


n, m = map(int, input().split())
sink = n - 1
edges = [[] for _ in range(n)]

hierarchy = [-1] * n

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

res = 0
while hierarchize(0):
    res += augment(0, 10000001)
print(res)

Submission status: Runtime Error

Solution code:
import sys
from queue import deque

sys.setrecursionlimit(500000)


def hierarchize(source):
    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, limit):
    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


n, m = map(int, input().split())
sink = n - 1
edges = [[] for _ in range(n)]

hierarchy = [-1] * n

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

res = 0
while hierarchize(0):
    res += augment(0, 10000001)
print(res)

Submission status: Runtime Error

Solution code:
def hierarchize(source):
    global edges, hierarchy
    l, r = 0, 1
    hierarchy = [-1] * n
    hierarchy[source] = 0
    queue[0] = source
    while l != r:
        v = queue[l]
        l += 1
        if v == sink:
            break
        for remain, target, idx in edges[v]:
            if hierarchy[target] == -1 and remain != 0:
                hierarchy[target] = hierarchy[v] + 1
                queue[r] = target
                r += 1
    return hierarchy[sink] != -1


def augment(v, limit):
    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


n, m = map(int, input().split())
sink = n - 1
edges = [[] for _ in range(n)]

queue = [-1] * n
hierarchy = [-1] * n

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

res = 0
while hierarchize(0):
    res += augment(0, 10000001)
print(res)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# Based on https://en.wikipedia.org/wiki/Ford???Fulkerson_algorithm

import collections
import sys
import uuid


REC_LIMIT = 10000


class Edge(object):

    def __init__(self, source, sink, capacity):
        self.source = source
        self.sink = sink
        self.capacity = capacity
        self.rev_edge = None
        self.edge_id = uuid.uuid4()

    def __str__(self):
        return "Edge {} -> {} : {}".format(self.source,
                                           self.sink, self.capacity)


class Network(object):

    def __init__(self):
        self.adj_edges = collections.defaultdict(list)
        self.flow = dict()
        self.used_edge = None

    def get_edges_from(self, vertex):
        return self.adj_edges[vertex]

    def add_edge(self, source, sink, capacity):
        assert source != sink
        f_edge = Edge(source, sink, capacity)
        b_edge = Edge(sink, source, 0)
        f_edge.rev_edge = b_edge
        b_edge.rev_edge = f_edge
        self.adj_edges[source].append(f_edge)
        self.adj_edges[sink].append(b_edge)
        self.flow[f_edge] = 0
        self.flow[b_edge] = 0

    def find_path_rec(self, source, sink, path):
        if source == sink:
            return path
        for edge in self.get_edges_from(source):
            residual = edge.capacity - self.flow[edge]
            if residual > 0 and not self.used_edge[edge.edge_id]:
                self.used_edge[edge.edge_id] = True
                result = self.find_path_rec(edge.sink, sink, path + [edge])
                if result is not None:
                    return result

    def find_path(self, *args):
        self.used_edge = collections.defaultdict(bool)
        return self.find_path_rec(*args)

    def max_flow(self, source, sink):
        while True:
            path = self.find_path(source, sink, [])
            if path is None:
                break
            flow = min(edge.capacity - self.flow[edge] for edge in path)
            for edge in path:
                self.flow[edge] += flow
                self.flow[edge.rev_edge] -= flow
        return sum(self.flow[edge] for edge in self.get_edges_from(source))


def main():
    v, e = map(int, input().split())
    network = Network()
    for _ in range(e):
        network.add_edge(*map(int, input().split()))
    mf = network.max_flow(0, v - 1)
    print(mf)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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

output:
3
"""

import sys
from collections import deque


def graph_bfs(source, target, parent):
    visited = [False] * v_num
    queue = deque()
    queue.appendleft(source)
    visited[source] = True

    while queue:
        current = queue.popleft()
        for adj, cp in adj_table[current].items():
            if cp and not visited[adj]:
                queue.append(adj)
                visited[adj] = True
                parent[adj] = current

    return True if visited[target] else False


def graphFordFulkerson(source, sink):
    parent = [-1] * v_num
    max_flow = 0

    while graph_bfs(source, sink, parent):
        path_flow = float('inf')

        bk_1 = sink
        while bk_1 is not source:
            path_flow = min(path_flow, adj_table[parent[bk_1]][bk_1])
            bk_1 = parent[bk_1]

        max_flow += path_flow

        bk_2 = sink
        while bk_2 is not source:
            parent_bk_2 = parent[bk_2]
            assert parent_bk_2 != -1
            adj_table[parent_bk_2].setdefault(bk_2, 0)
            # adj_table[bk_2].setdefault(parent_bk_2, 0)

            # print(bk_2, parent_bk_2, path_flow, bk_1, parent[bk_1], parent, adj_table)
            adj_table[parent_bk_2][bk_2] -= path_flow
            adj_table[bk_2][parent_bk_2] += path_flow
            bk_2 = parent[bk_2]

    return max_flow


def generate_adj_table(_edges):
    for edge in _edges:
        source, target, cp = map(int, edge)
        init_adj_table[source][target] = cp

    return init_adj_table


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    v_num, e_num = map(int, _input[0].split())
    edges = map(lambda x: x.split(), _input[1:])

    init_adj_table = [dict() for _ in range(v_num)]
    adj_table = generate_adj_table(edges)
    ans = graphFordFulkerson(source=0, sink=v_num - 1)
    print(ans)