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:
#edge = [[from, to, v]]

INF = 10**9
N = 100

used = [False] * N
G = [[]]*N

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

    return 0

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

if __name__ == "__main__":
    V, E = map(int, input().split())
    for i in range(E):
        u, v, c = map(int, input().split())
        l = len(G[v])
        G[u].append([v, c, l])
        G[v].append([u, 0, l])
    print(max_flow(0, V-1))

Submission status: Wrong Answer

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

used = [False] * N
G = [[]]*N

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

    return 0

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

if __name__ == "__main__":
    V, E = map(int, input().split())
    for i in range(E):
        u, v, c = map(int, input().split())
        l = len(G[v])
        G[u].append([v, c, l])
        G[v].append([u, 0, l])
    print(max_flow(0, V-1))

Submission status: Wrong Answer

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

used = [False] * N
G = [[]]*N

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

    return 0

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

if __name__ == "__main__":
    V, E = map(int, input().split())
    for i in range(E):
        u, v, c = map(int, input().split())
        l = len(G[v])
        G[u].append([v, c, l])
        G[v].append([u, 0, l])
    print(max_flow(0, V-1))

Submission status: Wrong Answer

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

used = [False] * N
G = [[]]*N

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

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

if __name__ == "__main__":
    V, E = map(int, input().split())
    for i in range(E):
        u, v, c = map(int, input().split())
        l = len(G[v])
        G[u].append([v, c, l])
        G[v].append([u, 0, l])
    print(max_flow(0, V-1))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop


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

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

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

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

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


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

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

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


def max_flow(network, s, t):
    def augment_path():
        marked = [False] * network.v
        edge_to = [None] * network.v
        heap = [(0, s, 0, None)]
        while heap:
            cap, v, n, e = heappop(heap)
            cap = -cap
            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, (min(-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: Wrong Answer

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,0])
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[x][j][2] += 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: Wrong Answer

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

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


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

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

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

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:
                f = self.dfs(s, t, float('inf'))
                if f == 0:
                    break
                flow += f


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

Solution code:
from sys import stdin
from collections import defaultdict
readline = stdin.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()
        if u in route:
            continue
        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: Wrong Answer

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

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)]
    flow = [[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

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

    print(sum(flow[i][source] 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:
                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: Wrong Answer

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

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

Solution code:
from sys import stdin
from collections import defaultdict
readline = stdin.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

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

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

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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):
    '''C[u][v] > 0 and C[v][u] > 0 ??¨?????????????????? antiparallel ????¨±????????????
    '''
    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):
        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: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
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.ford_fulkerson(source, sink)

    def ford_fulkerson(self, source, sink):
        """find max-flow"""
        

        INF = float('inf')
        maxflow = 0
        while True:
            self.used = [False] * self.V
            flow = dfs(source, sink, INF)
            if flow == 0:
                return maxflow
            else:
                maxflow += flow
    def dfs(self, vertex, sink, flow):
        """find augmenting path"""
        if vertex == sink:
            return flow
        self.used[vertex] = True
        for i, e in enumerate(self.E[vertex]):
            if not sekf.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

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush


def decrease_flow(route):
    global edges, total_flow
    min_flow = min(edges[n1][n2] for n1, n2 in zip(route, route[1:]))
    if min_flow:
        total_flow += min_flow
        for n1, n2 in zip(route, route[1:]):
            edges[n1][n2] -= min_flow


def bfs(source):
    global edges, sink
    queue = [(0, source, tuple())]
    while queue:
        hops, node, route = heappop(queue)
        if node == sink:
            decrease_flow(route)
        for i, f in enumerate(edges[node]):
            if not f or i in route:
                continue
            heappush(queue, (hops + 1, i, route + (i,)))


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

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

bfs(0)

print(total_flow)

Submission status: Wrong Answer

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


def augment(v, limit):
    global sink, edges, hierarchy
    if v == sink:
        return limit
    res = 0
    for e in edges[v]:
        remain, target, idx = e
        if remain == 0 or hierarchy[v] >= hierarchy[target]:
            continue
        aug = augment(target, min(limit, remain))
        e[0] -= aug
        edges[target][idx][0] += aug
        res += aug
        limit -= aug
        if not limit:
            break
    return res


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

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

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

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

Submission status: Wrong Answer

Solution code:
n, q = list(map(int, input().split(' ')))

process = []
for i in range(n):    
    process.append(input().split(' '))
    process[i][1] = int(process[i][1])

timer = 0
fin_time = []
num_of_proc = n    
while num_of_proc > 0:
    for i in range(n):
        if process[i][1] == 0:
          continue  
        elif process[i][1] <= q:
            num_of_proc -= 1
            timer += process[i][1]
            process[i][1] = 0
            fin_time.append([process[i][0], timer])
        else:
            timer += q
            process[i][1] -= q

for t in fin_time:
    print(t[0], t[1])

Submission status: Wrong Answer

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

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

        max_flow += path_flow

        bk_2 = sink
        while bk_2 is not source:
            parent_bk_2 = parent[bk_2]
            adj_table[parent_bk_2].setdefault(bk_2, path_flow)
            adj_table[bk_2].setdefault(parent_bk_2, path_flow)

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

    return max_flow


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