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: Wrong Answer

Solution code:
# Acceptance of input

import sys

file_input = sys.stdin

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

digraph = [[None] * V for i in range(V)]

for line in file_input:
    u, v, c = map(int, line.split())
    digraph[u][v] = [0, c] # [flow, capacity]

# Ford???Fulkerson algorithm

# dfs for residual capacity network
def search(goal, path, min_capacity):
    n = path[-1]
    if n == goal:
        path.append(min_capacity)
        return path
    else:
        for i in range(V):
            if i not in path:
                a = digraph[n][i]
                if a:
                    r = a[1] - a[0]
                    if r > 0:
                        path.append(i)
                        min_capacity = min(min_capacity, r)
                        return search(goal, path, min_capacity)
                        path.pop()
                a_rev = digraph[i][n]
                if a_rev:
                    r = a_rev[1] - a_rev[0]
                    if r > 0:
                        path.append(i)
                        min_capacity = min(min_capacity, r)
                        return search(goal, path, min_capacity)
                        path.pop()

def ford_fulkerson(s, t, f):
    aug_path = search(t, [s], 10000)
    if aug_path == None:
        return f
    cfp = aug_path.pop()
    for i, j in zip(aug_path[:-1], aug_path[1:]):
        a = digraph[i][j]
        if a:
            a[0] += cfp
        a_rev = digraph[j][i]
        if a_rev:
            a_rev[0] -= cfp
    f += cfp
    return ford_fulkerson(s, t, f)

# output
print(ford_fulkerson(0, V - 1, 0))

Submission status: Time Limit Exceeded

Solution code:
import sys


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 = []
        self._level[start] = 0
        que.append(start)
        while que:
            cur_vertex = que[-1]
            que.pop()
            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
        for e in self._graph[cur_vertex][self._iter[cur_vertex]:len(self._graph[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
        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: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict
readline = stdin.readline




#readline = open('???.txt').readline

def main():
    v, e = map(int, readline().split())
    residual_flow = [[0] * v for _ in range(v)]
    g = defaultdict(list)
    source, sink = 0, v - 1

    for _ in range(e):
        s, t, c = map(int, readline().split())
        if 0 < c:
            g[s].append(t)
            residual_flow[s][t] = c

    while True:
        route, flow = search(g, residual_flow, source, sink)
        if route is None:
            break
        for i in range(1, len(route)):
            residual_flow[route[i - 1]][route[i]] -= flow
            residual_flow[route[i]][route[i - 1]] += flow

    print(sum(residual_flow[i][source] for i in g[source]))

def search(g, residual, source, sink):
    dfs_stack = [(source, None, float('inf'))]
    route = [None]
    while dfs_stack:
        u, prev, flow = dfs_stack.pop()
        while route[-1] != prev:
            route.pop()
        if u in route:
            continue
        
        route.append(u)
        if u == sink:
            return route[1:], flow
        for v in g[u]:
            next_flow = min(residual[u][v], flow)
            if 0 < next_flow:
                dfs_stack.append((v, u, next_flow))
    return None, None
main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict
readline = stdin.readline


#readline = open('???.txt').readline

def main():
    v, e = map(int, readline().split())
    residual_flow = [[0] * v for _ in range(v)]
    g = defaultdict(list)
    source, sink = 0, v - 1

    for _ in range(e):
        s, t, c = map(int, readline().split())
        if 0 < c:
            g[s].append(t)
            residual_flow[s][t] = c

    while True:
        route, flow = search(g, residual_flow, source, sink)
        if route is None:
            break
        for i in range(1, len(route)):
            residual_flow[route[i - 1]][route[i]] -= flow
            residual_flow[route[i]][route[i - 1]] += flow

    print(sum(residual_flow[i][source] for i in g[source]))

def search(g, residual, source, sink):
    dfs_stack = [(source, None, float('inf'))]
    route = [None]
    while dfs_stack:
        u, prev, flow = dfs_stack.pop()
        while route[-1] != prev:
            route.pop()
        route.append(u)
        if u == sink:
            return route[1:], flow
        for v in g[u]:
            if v in route:
                continue
            next_flow = min(residual[u][v], flow)
            if 0 < next_flow:
                dfs_stack.append((v, u, next_flow))
    return None, None
main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict
readline = stdin.readline



#readline = open('???.txt').readline

def main():
    v, e = map(int, readline().split())
    g = defaultdict(list)
    residual = [[0] * v for _ in range(v)]
    source, sink = 0, v - 1

    for _ in range(e):
        s, t, c = map(int, readline().split())
        if 0 < c:
            g[s].append(t)
            residual[s][t] = c

    capacity = sum(residual[source][i] for i in g[source])

    while True:
        route, flow = search(g, residual, source, sink)
        if route is None:
            break
        for i in range(1, len(route)):
            residual[route[i - 1]][route[i]] -= flow

    print(capacity - sum(residual[source][i] for i in g[source]))

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 in visited:
            if v in route:
                continue
            next_flow = min(residual[u][v], flow)
            if 0 < next_flow:
                dfs_stack.append((v, u, next_flow))
    return None, None
main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict
readline = stdin.readline



#readline = open('???.txt').readline

def main():
    v, e = map(int, readline().split())
    g = defaultdict(list)
    residual = [[0] * v for _ in range(v)]
    source, sink = 0, v - 1

    for _ in range(e):
        s, t, c = map(int, readline().split())
        if 0 < c:
            g[s].append(t)
            g[t].append(s)
            residual[s][t] = c

    capacity = sum(residual[source][i] for i in g[source])

    while True:
        route, flow = search(g, residual, source, sink)
        if route is None:
            break
        for i in range(1, len(route)):
            residual[route[i - 1]][route[i]] -= flow
            residual[route[i]][route[i - 1]] += flow
    print(capacity - sum(residual[source][i] for i in g[source]))

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 in route:
                continue
            next_flow = min(residual[u][v], flow)
            if 0 < next_flow:
                dfs_stack.append((v, u, next_flow))
    return None, None
main()

Submission status: Time Limit Exceeded

Solution code:
def ford_fulkerson(graph, source, sink):
    def dfs(cur_node, visited):
        if cur_node == sink:
            return []
        for next_node, v in enumerate(graph[cur_node]):
            if visited[next_node] or v <= 0:
                continue
            visited[next_node] = True
            ret = dfs(next_node, visited)
            visited[next_node] = False
            if ret is not None:
                return [cur_node] + ret 
        return None
    N = len(graph)
    while True:
        route = dfs(source, [False]*N)
        if route is None:
            break
        v = min(graph[s][t] for s, t in zip(route, route[1:]))
        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__":
    main()

Submission status: Time Limit Exceeded

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] == -1:
                return maxflow
            self.itr = [0] * self.V
            while True:
                flow = self.dfs(source, sink, INF)
                if flow == 0:
                    break
                else:
                    maxflow += flow
            

    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:
                    e.cap -= 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] == -1:
                    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: Time Limit Exceeded

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:
                    e.cap -= 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: Time Limit Exceeded

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].cap -= 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: Time Limit Exceeded

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():
    sys.setrecursionlimit(REC_LIMIT)
    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: Time Limit Exceeded

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] * vertices
    queue = deque()
    queue.append(source)
    visited[source] = True

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

    return True if visited[target] else False


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

    while graph_bfs(source, sink, parent):
        path_flow = float('inf')
        end = sink
        while end is not source:
            path_flow = min(path_flow, adj_table[parent[end]][end])
            end = parent[end]

        max_flow += path_flow
        cursor = sink
        while cursor is not source:
            c_parent = parent[cursor]
            # print(c_parent, cursor, path_flow)
            adj_table[c_parent].setdefault(cursor, -1)
            adj_table[cursor].setdefault(c_parent, -1)
            
            adj_table[c_parent][cursor] -= path_flow
            adj_table[cursor][c_parent] += path_flow
            cursor = parent[c_parent]

    return max_flow


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

    return init_adj_table


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

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

Submission status: Time Limit Exceeded

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 bfs(source, target):
    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 graph_FordFulkerson(source, sink):
    max_flow = 0

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

        # 1st backward traversal
        bk_1 = sink
        while bk_1 != source:
            parent_bk_1 = parent[bk_1]
            assert parent_bk_1 != -1
            path_flow = min(path_flow, adj_table[parent_bk_1][bk_1])
            bk_1 = parent[bk_1]

        max_flow += path_flow

        # 2nd backward traversal
        bk_2 = sink
        while bk_2 != source:
            parent_bk_2 = parent[bk_2]
            assert parent_bk_2 != -1
            adj_table[bk_2].setdefault(parent_bk_2, 0)
            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


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

    adj_table = tuple(dict() for _ in range(v_num))
    for edge in edges:
        s, t, c = map(int, edge)
        adj_table[s][t] = c

    parent = [-1] * v_num
    visited = [False] * v_num

    print(graph_FordFulkerson(source=0, sink=v_num - 1))

Submission status: Time Limit Exceeded

Solution code:
# Acceptance of input

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

# Dinic's algorithm

import collections

# BFS for residual capacity network to construct level graph
def bfs(start, goal, parent):
    level = [V] * V
    queue = collections.deque()
    queue.append(start)
    level[start] = 0
    while queue:
        u = queue.popleft()
        next_level = level[u] + 1
        for v, flow in enumerate(adj_mat[u]):
            if (level[v] >= next_level) and (flow > 0):
                queue.append(v)
                level[v] = next_level
                parent[v].append(u)
    return level[goal]

# DFS for level graph to construct blocking flow
# search in reverse direction from sink
def dfs(start, goal, path, parent, aug_path_flow, blocking_flow):
    v = path[-1]
    if v == goal:
        blocking_flow[0] += aug_path_flow
        for x, y in zip(path[1:], path[:-1]):
            adj_mat[x][y] -= aug_path_flow
            adj_mat[y][x] += aug_path_flow
    else:
        for u in parent[v]:
            path.append(u)
            dfs(start, goal, path, parent,
                min(aug_path_flow, adj_mat[u][v]), blocking_flow)
            path.pop()

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

# output
print(dinic(0, V - 1))

Submission status: Time Limit Exceeded

Solution code:
# Acceptance of input

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

# Dinic's algorithm

import collections

# BFS for residual capacity network to construct level graph
def bfs(start, goal, parent):
    level = [V] * V
    queue = collections.deque()
    queue.append(start)
    level[start] = 0
    while queue:
        u = queue.popleft()
        next_level = level[u] + 1
        for v, flow in enumerate(adj_mat[u]):
            if (level[v] >= next_level) and (flow > 0):
                queue.append(v)
                level[v] = next_level
                parent[v].append(u)
    return level[goal]

# DFS for level graph and construct blocking flow
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]
        # search in reverse direction from sink
        dfs(source, path, parent, blocking_flow)
        max_flow += blocking_flow[0]
        parent = [[] for i in range(V)]
    return max_flow

# output
print(dinic(0, V - 1))

Submission status: Time Limit Exceeded

Solution code:
# Acceptance of input

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

# Dinic's algorithm

import collections

# BFS for residual capacity network to construct level graph
def bfs(start, goal, parent):
    level = [V] * V
    queue = collections.deque()
    queue.append(start)
    level[start] = 0
    while queue:
        u = queue.popleft()
        next_level = level[u] + 1
        for v, flow in enumerate(adj_mat[u]):
            if (level[v] >= next_level) and (flow > 0):
                queue.append(v)
                level[v] = next_level
                parent[v].append(u)
    return level[goal]

# DFS for level graph and construct blocking flow
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])
            if not aug_path_flow:
                break
        if aug_path_flow:
            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]
        # search in reverse direction from sink
        dfs(source, path, parent, blocking_flow)
        max_flow += blocking_flow[0]
        parent = [[] for i in range(V)]
    return max_flow

# output
print(dinic(0, V - 1))