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:
def main():
    nvertices, nedges = map(int, input().split())
    adj = [[0] * nvertices for i in range(nvertices)]
    for i in range(nedges):
        u, v, c = map(int, input().split())
        adj[u][v] = c

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

    print(ans)


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

    return None


main()

Submission status: Accepted

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

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

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

    print(ans)


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

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

    return None


main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

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

Submission status: Accepted

Solution code:
from collections import deque


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


# 最大流問題を解く O(|E||V|^2)
class Dinic:
    def __init__(self, num_of_node: int):
        assert num_of_node > 0

        self.graph = [list() for _ in range(num_of_node)]   # グラフの隣接リスト表現
        self.level = [None] * num_of_node      # sからの距離
        self.ite = [None] * num_of_node       # どこまで調べ終わったか

    # fromからtoへ向かう容量capの辺をグラフに追加する
    def add_edge(self, f: int, t: int, cap: int):
        self.graph[f].append(Edge(t, len(self.graph[t]), cap))
        self.graph[t].append(Edge(f, len(self.graph[f]) - 1, 0))

    # sからtへの最大流を求める
    def max_flow(self, s: int, t: int):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0:
                return flow

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

    # sからの最短距離をBFSで計算する
    def bfs(self, s: int):
        self.level = [-1] * len(self.level)
        que = deque()
        que.append(s)
        self.level[s] = 0
        while len(que):
            v = que.popleft()

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

    # 増加パスをDFSで探す
    def dfs(self, v: int, t: int, f: int):
        if v == t:
            return f

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


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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque


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


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

        self.graph = [list() for _ in range(num_of_node)]   # グラフの隣接リスト表現
        self.level = [None] * num_of_node      # sからの距離
        self.ite = [None] * num_of_node       # どこまで調べ終わったか

    # fromからtoへ向かう容量capの辺をグラフに追加する
    def add_edge(self, f: int, t: int, cap: int):
        self.graph[f].append(Edge(t, 0, cap, len(self.graph[t]), False))
        self.graph[t].append(Edge(f, cap, cap, len(self.graph[f]) - 1, True))

    # sからtへの最大流を求める
    def max_flow(self, s: int, t: int):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0:
                return flow

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

    # sからの最短距離をBFSで計算する
    def bfs(self, s: int):
        self.level = [-1] * len(self.level)
        que = deque()
        que.append(s)
        self.level[s] = 0
        while len(que):
            v = que.popleft()

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

    # 増加パスをDFSで探す
    def dfs(self, v: int, t: int, f: int):
        if v == t:
            return f

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


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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Network Flow - Maximum Flow
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A&lang=jp

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

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

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


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


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


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

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

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


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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Network Flow - Maximum Flow
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A&lang=jp

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

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


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


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


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

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


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

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

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


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

Submission status: Accepted

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

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

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


# 豎守畑迚・ edge縺ｯN*N縺ｮ2谺｡蜈・・蛻・ cap縺ｧ騾溘￥縺ｪ縺｣縺・
class Flow():
    def __init__(self, e, N):
        self.E = e
        self.N = N

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

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

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

        return r

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

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

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

    return r

# start = time.time()
print(main())
# pe(time.time() - start)

Submission status: Accepted

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

from collections import deque

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

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

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

import sys
input = sys.stdin.readline

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

d = Dinic(N)

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

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

Submission status: Accepted

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

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

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

            if maxflow <= 0:
                return realflow

    return realflow

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

    N = len(cost)
    ans = 0

    while True:

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

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

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

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


######MAIN#######

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

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

for i in range(M):

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

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

Submission status: Accepted

Solution code:
from collections import deque


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

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

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

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

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


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


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

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

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
INF = 10 ** 10
edges = defaultdict(dict)


def add_edge(frm, to, capacity):
    edges[frm][to] = capacity
    edges[to][frm] = 0


def bfs(start, goal):
    """
    update: distance_from_start
    return bool: can reach to goal
    """
    global distance_from_start
    distance_from_start = [-1] * len(edges)
    queue = deque()
    distance_from_start[start] = 0
    queue.append(start)
    while queue and distance_from_start[goal] == -1:
        frm = queue.popleft()
        for to in edges[frm]:
            if edges[frm][to] > 0 and distance_from_start[to] == -1:
                distance_from_start[to] = distance_from_start[frm] + 1
                queue.append(to)

    return distance_from_start[goal] != -1


def dfs(current, goal, flow):
    """
    make flow from `current` to `goal`
    update: capacity of edges, iteration_count
    return: flow (if impossible: 0)
    """
    if current == goal:
        return flow
    i = itertion_count[current]
    while itertion_count[current] < len(edges[current]):
        to = edges_index[current][i]
        capacity = edges[current][to]
        if capacity > 0 and distance_from_start[current] < distance_from_start[to]:
            d = dfs(to, goal, min(flow, capacity))
            if d > 0:
                edges[current][to] -= d
                edges[to][current] += d
                return d
        itertion_count[current] += 1
        i += 1
    return 0


def max_flow(start, goal):
    """
    return: max flow from `start` to `goal`
    """
    global itertion_count, edges_index
    flow = 0
    edges_index = {
        frm: list(edges[frm]) for frm in edges
    }
    while bfs(start, goal):
        itertion_count = [0] * len(edges)
        f = dfs(start, goal, INF)
        while f > 0:
            flow += f
            f = dfs(start, goal, INF)
    return flow


def main():
    # Verified: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/6/GRL_6_A
    V, E = map(int, input().split())
    for _i in range(E):
        v1, v2, capacity = map(int, input().split())
        add_edge(v1, v2, capacity)
    print(max_flow(0, V - 1))


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
    route = [0 for i in range(N)]   #ルート
    route[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容量)
                route[t] = s
                queue.append([t,flow])
                ed[t] = False
                if t == Goal: #ゴール到達
                    ans += flow
                    break
        else:
            continue
        break
    else:
        return False
    #ラインの更新
    t = Goal
    s = route[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 = route[t]
        
    return True

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

Submission status: Accepted

Solution code:
class Dinic:
  def __init__(self,n,g):
    self.n=n;self.e=[[]for _ in range(n)]
    for i in range(n):
      for j,c in g[i]:a=[j,c,None];a[2]=b=[i,0,a];self.e[i].append(a);self.e[j].append(b)
  def bfs(self,s,t):
    self.d=d=[None]*self.n;d[s]=0;k=[s];e=self.e
    for i in k:
      for j,c,_ in e[i]:
        if c and d[j]==None:d[j]=d[i]+1;k.append(j)
    return d[t]!=None
  def dfs(self,v,t,f):
    if v==t:return f
    d=self.d
    for e in self.m[v]:
      w,c,r=e
      if c and d[v]<d[w]:
        b=self.dfs(w,t,min(f,c))
        if b:e[1]-=b;r[1]+=b;return b
    return 0
  def flow(self,s,t):
    l=0;x=10**20
    while self.bfs(s,t):
      self.m=list(map(iter,self.e));f=x
      while f:f=self.dfs(s,t,x);l+=f
    return l
v,e=map(int,input().split())
edge=[[]for _ in range(v)]
for _ in range(e):
  uu,vv,c=map(int,input().split())
  edge[uu].append((vv,c))
dinic=Dinic(v,edge)
print(dinic.flow(0,v-1))

Submission status: Accepted

Solution code:
# maximum flow
# O(EV^2)

class Dinic():
    def __init__(self, N, INF=10**18):
        self.INF = INF
        self.graph = [{} for _ in range(N)]
        self.N = N
        self.level = [-1]*N
    
    def add_edge(self, u, v, cap, undirected=False):
        # u -> v (maxflow: cap)
        if cap == 0: return
        if undirected:
            self.graph[u][v] = cap
            self.graph[v][u] = cap
        elif v in self.graph[u]:
            self.graph[u][v] = cap
        else:
            self.graph[u][v] = cap
            self.graph[v][u] = 0
    
    def construct(self):
        self.orderedgraph = [[] for _ in range(self.N)]
        for v in range(self.N):
            self.orderedgraph[v] = list(self.graph[v].keys())

    # make level
    def bfs(self, start):
        self.level = [-1]*self.N
        self.que = [start]
        self.level[start] = 0
        while self.que:
            qq = []
            for p in self.que:
                for np, ncap in self.graph[p].items():
                    if ncap > 0 and self.level[np] == -1:
                        self.level[np] = self.level[p] + 1
                        qq.append(np)
            self.que = qq

    def dfs(self, start, finish):
        self.Flow = [self.INF]*self.N
        self.iter = [0]*self.N
        self.Par = [-1]*self.N
        self.stack = [start]
        while self.stack:
            v = self.stack.pop()
            if v == finish:
                d = self.Flow[v]
                while v != start:
                    nv = self.Par[v]
                    self.graph[nv][v] -= d
                    self.graph[v][nv] += d # inverse edge
                    v = nv
                return d
            # for nv, ncap in self.graph[v].items():
            for i in range(self.iter[v], len(self.orderedgraph[v])):
                self.iter[v] = i
                nv = self.orderedgraph[v][i]; ncap = self.graph[v][nv]
                if ncap > 0 and self.level[v] < self.level[nv]:
                    self.stack.append(nv)
                    self.Par[nv] = v
                    self.Flow[nv] = min(self.Flow[v], ncap)
        return 0

    # solve
    def flow(self, start, finish):
        self.construct()
        flow = 0
        while True:
            self.bfs(start)
            if self.level[finish] < 0: return flow
            while True:
                f = self.dfs(start, finish)
                if f == 0: break
                flow += f


if __name__=="__main__":
    import sys
    input = sys.stdin.readline

    N, M = map(int, input().split())
    ff = Dinic(N)
    for _ in range(M):
        a, b, c = map(int, input().split())
        ff.add_edge(a, b, c)
    print(ff.flow(0, N-1))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
INF = float('inf')


class FordFulkerson:
    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def dfs(self, v, t, f):
        if v == t:
            return f
        used = self.used
        used[v] = 1
        for e in self.G[v]:
            w, cap, rev = e
            if cap and not used[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

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

def main():
    V, E = map(int, readline().split())
    FF = FordFulkerson(V)
    for _ in range(E):
        u, v, cap = map(int, readline().split())
        FF.add_edge(u,v,cap)

    ans = FF.flow(0,V-1)
    print(ans)

if __name__ == '__main__':
    main()