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

Submission status: Memory Limit Exceeded

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(1000000)
INF = 10 ** 20

V, E = map(int, input().split())
net = [{}  for _ in range(V)]
for _ in range(E):
  u, v, c = map(int, input().split())
  net[u][v] = c
  net[v][u] = 0

start = 0
goal  = V - 1
def check_net(node, path, capacity):
  edges = net[node]
  for i in edges:
    cap = net[node][i]
    if cap != 0:
      if i == goal:
        return (path + [i], min(cap, capacity))
      else:
        return check_net(i, path + [i], min(cap, capacity))

  else:
    return ([], 0)

def update_net(path, capacity):
  for fromi, toi in zip(range(len(path) - 1), range(1, len(path))):
    fr, to = path[fromi], path[toi]
    net[fr][to] -= capacity
    net[to][fr] += capacity

i = 0
while True:
  path, cap = check_net(start, [], INF)
  if path == []:
    break
  update_net(path, cap)

print(sum(net[start]))

Submission status: Accepted

Solution code:
INF = 10**12
N = 101


class FordFulkerson:
    def __init__(self):
        self.G = [[] for _ in range(N)]
        self.used = [False] * N

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

    def dfs(self, s, t, f):
        if s == t:
            return f
        self.used[s] = True
        for i in range(len(self.G[s])):
            e = self.G[s][i]
            if not self.used[e[0]] and e[1] > 0:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d > 0:
                    self.G[s][i][1] -= d
                    self.G[e[0]][e[2]][1] += d
                    return d
        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.used = [False]*N
            f = self.dfs(s, t, INF)
            if f == 0:
                return flow
            flow += f

if __name__ == "__main__":
    V, E = map(int, input().split())
    ff = FordFulkerson()
    for i in range(E):
        u, v, c = map(int, input().split())
        ff.add_edge(u, v, c)
    print(ff.max_flow(0, V-1))

Submission status: Accepted

Solution code:
import sys
import queue


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 = queue.Queue()
        self._level[start] = 0
        que.put(start)
        while not que.empty():
            cur_vertex = que.get()
            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.put(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: 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
        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: 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 self._level[e.to] < 0 < e.cap:
                    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


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

if __name__ == '__main__':
    main()

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):
        for i in range(self._node):
            self._level[i] = -1
        que = deque()
        self._level[start] = 0
        que.append(start)
        while que:
            cur_vertex = que.popleft()
            for e in self._graph[cur_vertex]:
                if self._level[e.to] < 0 < e.cap:
                    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
            for i in range(self._node):
                self._iter[i] = 0
            while True:
                f = self.dfs(source, sink, self._inf)
                if f == 0:
                    break
                flow += f


def main():
    n, m = map(int, sys.stdin.readline().split())
    mf = MaxFlow(n, 10 ** 4)
    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))

if __name__ == '__main__':
    main()

Submission status: Accepted

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
        n = 0
        heap = [(-10**6, s, n, None)]
        while heap:
            cap, v, _, 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: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
n,e = map(int,input().split())
g = [[] for i in range(n)]
for i in range(e):
  a,b,c = map(int,input().split())
  g[a].append([b,c,len(g[b])])
  g[b].append([a,0,len(g[a])-1])
def dfs(x,t,f):
  if x == t:
    return f
  global used
  used[x] = 1
  for j in range(len(g[x])):
    y, cap, rev = g[x][j]
    if cap and not used[y]:
      d = dfs(y,t,min(f,cap))
      if d:
        g[x][j][1] -= d
        g[y][rev][1] += d
        return d
  return 0

flow = 0
f = INF = float("inf")
while f:
  used = [0]*n
  f = dfs(0,n-1,INF)
  flow += f
  
print(flow)

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(200000)
n,e = map(int,input().split())
g = [[] for i in range(n)]
for i in range(e):
  a,b,c = map(int,input().split())
  g[a].append([b,c,len(g[b])])
  g[b].append([a,0,len(g[a])-1])
  
def bfs(s,t):
  global level
  que = deque([s])
  level[s] = 0
  while que:
    v = que.popleft()
    lv = level[v] +1
    for y, cap, rev in g[v]:
      if cap and level[y] is None:
        level[y] = lv
        que.append(y)
  return level[t] if level[t] else 0
def dfs(x,t,f):
  if x == t:
    return f
  for j in range(it[x],len(g[x])):
    it[x] = j
    y, cap, rev = g[x][j]
    if cap and level[x] < level[y]:
      d = dfs(y,t,min(f,cap))
      if d:
        g[x][j][1] -= d
        g[y][rev][1] += d
        return d
  return 0
 
flow = 0
f = INF = float("inf")
level = [None]*n
while bfs(0,n-1):
  it = [0]* n
  f = INF
  while f:
    f = dfs(0,n-1,INF)
    flow += f
  level = [None]*n
print(flow)

Submission status: Accepted

Solution code:
from collections import defaultdict

def bfs(start, end, connect, v_num, flow):
    level = [-1] * v_num
    level[start] = 0
    queue = [start]
    while queue:
        v = queue.pop()
        for next_v in connect[v]:
            if flow[v][next_v] > 0 and level[next_v] < 0:
                level[next_v] = level[v] + 1
                queue.append(next_v)
    return level

def dfs(here, end, connect, level, flow, minimum_f, visited):
    if here == end:
        return minimum_f
    for next_v in connect[here]:
        if not visited[here][next_v] and flow[here][next_v] > 0 and level[here] < level[next_v]:
            visited[here][next_v] = 1
            temp_f = dfs(next_v, end, connect, level, flow, min(flow[here][next_v], minimum_f), visited)
            if temp_f:
                flow[here][next_v] -= temp_f
                flow[next_v][here] += temp_f
                # print(flow)
                return temp_f
    return 0

v_num, e_num = (int(n) for n in input().split(" "))
connect = defaultdict(list)
flow = defaultdict(lambda: defaultdict(int))
for _ in range(e_num):
    s, t, c = map(int, input().split(" "))
    connect[s].append(t)
    connect[t].append(s)
    flow[s][t] = c
start = 0
end = v_num - 1
answer = 0
while True:
    level = bfs(start, end, connect, v_num, flow)
    if level[end] < 0:
        print(answer)
        break
    visited = defaultdict(lambda: defaultdict(int))
    temp_f = dfs(start, end, connect, level, flow, float("inf"), visited)
    while temp_f > 0:
        answer += temp_f
        temp_f = dfs(start, end, connect, level, flow, float("inf"), visited)

Submission status: Accepted

Solution code:

from collections import deque
INF = float("inf")
TO = 0;  CAP = 1;  REV = 2
class Dinic:
    def __init__(self, N):
        self.N = N
        self.V = [[] for _ in range(N)]  # to, cap, rev
        # 辺 e = V[n][m] の逆辺は V[e[TO]][e[REV]]
        self.level = [0] * N

    def add_edge(self, u, v, cap):
        self.V[u].append([v, cap, len(self.V[v])])
        self.V[v].append([u, 0, len(self.V[u])-1])

    def bfs(self, s: int) -> bool:
        self.level = [-1] * self.N
        self.level[s] = 0
        q = deque()
        q.append(s)
        while len(q) != 0:
            v = q.popleft()
            for e in self.V[v]:
                if e[CAP] > 0 and self.level[e[TO]] == -1:  # capが1以上で未探索の辺
                    self.level[e[TO]] = self.level[v] + 1
                    q.append(e[TO])
        return True if self.level[self.g] != -1 else False  # 到達可能

    def dfs(self, v: int, f) -> int:
        if v == self.g:
            return f
        for i in range(self.ite[v], len(self.V[v])):
            self.ite[v] = i
            e = self.V[v][i]
            if e[CAP] > 0 and self.level[v] < self.level[e[TO]]:
                d = self.dfs(e[TO], min(f, e[CAP]))
                if d > 0:  # 増加路
                    e[CAP] -= d  # cap を減らす
                    self.V[e[TO]][e[REV]][CAP] += d  # 反対方向の cap を増やす
                    return d
        return 0

    def solve(self, s, g):
        self.g = g
        flow = 0
        while self.bfs(0):  # 到達可能な間
            self.ite = [0] * self.N
            f = self.dfs(s, INF)
            while f > 0:
                flow += f
                f = self.dfs(s, INF)
        return flow


v, e = map(int, input().split())
dinic = Dinic(v)
for _ in range(e):
    dinic.add_edge(*map(int, input().split()))
print(dinic.solve(0, v-1))

Submission status: Accepted

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 for _ in range(self.N)]
        self.iter = [0 for _ in range(self.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, 0, len(self.edges[u])-1])
        else:  # TODO
            self.edges[u].append([v, c, len(self.edges[u])])

    def bfs(self, s):
        self.level = [-1 for _ in range(self.N)]
        self.level[s] = 0
        que = queue.Queue()
        que.put(s)
        while not que.empty():
            v = que.get(s)
            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 for _ in range(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: Accepted

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


def main():
    v, e = map(int, readline().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, readline().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:
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())
        C[u][v] = c
    return C, nV, 0, nV - 1

def dinic_ap(C, nV, s, t):
    '''allow antiparallel C[u][v] > 0 and C[v][u] > 0
    '''
    Cpp, nVpp = resolve_antiparallel(C, nV)
    return dinic(Cpp, nVpp, s, t)

def resolve_antiparallel(C, nV):
    Cpp = [dict() for i in range(nV)]
    new_v = nV
    for u in range(nV):
        for v, capacity in C[u].items():
            if capacity:
                if (u not in C[v]) or (u not in Cpp[v]):
                    Cpp[u][v] = capacity
                else:
                    Cpp.append(dict())
                    Cpp[u][new_v] = capacity
                    Cpp[new_v][v] = capacity
                    new_v += 1
    return Cpp, new_v

def dinic(C, nV, s, t):
    cf = [dict() for i in range(nV)]
    for u in range(nV):
        if u == t:
            continue
        for v, capacity in C[u].items():
            if capacity:
                cf[u][v] = capacity
                cf[v][u] = 0
    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_ap(C, nV, s, t))

Submission status: Accepted

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

    def __init__(self, v):
        self.V = v
        self.G = [[] for i in xrange(self.V)]

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

    def add_dual(self, frm, to, cap):
        self.G[frm].append(self.edge(to, len(self.G[to]), cap))
        self.G[to].append(self.edge(frm, len(self.G[frm]) - 1, cap))

    def bfs(self, s):
        self.level = [-1] * self.V
        self.level[s] = 0
        que = []
        que.append(s)
        while (que):
            v = que.pop(0)
            for i in xrange(len(self.G[v])):
                e = self.G[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, t, f):
        if v == t: return f
        for i in xrange(self.itr[v], len(self.G[v])):
            self.itr[v] = i
            e = self.G[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:
                    e.cap -= d
                    self.G[e.to][e.rev].cap += d
                    return d
        return 0

    def max_flow(self, s, t):
        inf = float("inf")
        flow = 0
        while 1:
            self.bfs(s)
            if self.level[t] < 0: return flow

            self.itr = [0] * self.V
            f = self.dfs(s, t, inf)
            while f > 0:
                flow += f
                f = self.dfs(s, t, inf)

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

Submission status: Accepted

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(V)]
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: Accepted

Solution code:
class FordFulkerson:
    """Ford-Fulkerson Algorithm: find max-flow
       complexity: O(FE) (F: max flow)
    """
    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.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, e in enumerate(self.E[vertex]):
                if not used[e.to] and e.cap > 0:
                    d = 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

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