Maximum Flow (Edmonds-Karp & Dinic) — Practice Tasks¶

import sys
from collections import deque


class Dinic:
    def __init__(self, n):
        self.n = n; self.to = []; self.cap = []; self.head = [[] for _ in range(n)]
    def add_edge(self, u, v, c):
        self.head[u].append(len(self.to)); self.to.append(v); self.cap.append(c)
        self.head[v].append(len(self.to)); self.to.append(u); self.cap.append(0)
    def bfs(self, s, t):
        self.level = [-1]*self.n; self.level[s] = 0; q = deque([s])
        while q:
            u = q.popleft()
            for e in self.head[u]:
                if self.cap[e] > 0 and self.level[self.to[e]] < 0:
                    self.level[self.to[e]] = self.level[u]+1; q.append(self.to[e])
        return self.level[t] >= 0
    def dfs(self, u, t, f):
        if u == t: return f
        while self.it[u] < len(self.head[u]):
            e = self.head[u][self.it[u]]; v = self.to[e]
            if self.cap[e] > 0 and self.level[v] == self.level[u]+1:
                p = self.dfs(v, t, min(f, self.cap[e]))
                if p > 0: self.cap[e] -= p; self.cap[e^1] += p; return p
            self.it[u] += 1
        return 0
    def max_flow(self, s, t):
        sys.setrecursionlimit(1 << 25); flow = 0
        while self.bfs(s, t):
            self.it = [0]*self.n
            while (f := self.dfs(s, t, float("inf"))): flow += f
        return flow


def main():
    data = sys.stdin.read().split()
    idx = 0
    def nxt():
        nonlocal idx; idx += 1; return int(data[idx-1])
    V, E, s, t = nxt(), nxt(), nxt(), nxt()
    d = Dinic(V)
    for _ in range(E):
        d.add_edge(nxt(), nxt(), nxt())
    print(d.max_flow(s, t))


main()

def verify(V, edges, s, t):
    # edges: list of (u, v, c, f)
    inflow = [0]*V; outflow = [0]*V
    for u, v, c, f in edges:
        if not (0 <= f <= c):
            return "INVALID"
        outflow[u] += f; inflow[v] += f
    for x in range(V):
        if x != s and x != t and inflow[x] != outflow[x]:
            return "INVALID"
    return "VALID"

def max_matching(L, R, pairs):
    s, t = L + R, L + R + 1
    d = Dinic(L + R + 2)
    for i in range(L): d.add_edge(s, i, 1)
    for j in range(R): d.add_edge(L + j, t, 1)
    for u, v in pairs: d.add_edge(u, L + v, 1)
    return d.max_flow(s, t)


# max_matching(3, 3, [(0,0),(0,1),(1,1),(2,2)]) == 3

def min_cut(d, s, original_edges):
    seen = [False]*d.n; stack = [s]; seen[s] = True
    while stack:
        u = stack.pop()
        for e in d.head[u]:
            if d.cap[e] > 0 and not seen[d.to[e]]:
                seen[d.to[e]] = True; stack.append(d.to[e])
    S = [v for v in range(d.n) if seen[v]]
    cut = [(u, v) for (u, v, c) in original_edges if seen[u] and not seen[v]]
    return S, cut

def edge_disjoint_paths(n, edges, s, t):
    d = Dinic(n)
    for u, v in edges:
        d.add_edge(u, v, 1)
    return d.max_flow(s, t)

def max_flow_vertex_caps(V, vcap, edges, s, t):
    d = Dinic(2 * V)
    for v in range(V):
        d.add_edge(2*v, 2*v + 1, vcap[v])     # v_in -> v_out
    for u, v, c in edges:
        d.add_edge(2*u + 1, 2*v, c)           # u_out -> v_in
    return d.max_flow(2*s + 1, 2*t)           # s_out -> t_in

def multi_source_sink(V, edges, sources, sinks):
    S, T = V, V + 1
    d = Dinic(V + 2)
    for (src, supply) in sources: d.add_edge(S, src, supply)
    for (snk, demand) in sinks:   d.add_edge(snk, T, demand)
    for u, v, c in edges:         d.add_edge(u, v, c)
    return d.max_flow(S, T)

def vertex_disjoint_paths(V, edges, s, t):
    INF = 1 << 30
    d = Dinic(2 * V)
    for v in range(V):
        cap = INF if v in (s, t) else 1
        d.add_edge(2*v, 2*v + 1, cap)
    for u, v in edges:
        d.add_edge(2*u + 1, 2*v, 1)
    return d.max_flow(2*s + 1, 2*t)

def min_path_cover(V, edges):
    # left v = v, right v = V + v, s = 2V, t = 2V+1
    s, t = 2*V, 2*V + 1
    d = Dinic(2*V + 2)
    for v in range(V):
        d.add_edge(s, v, 1)
        d.add_edge(V + v, t, 1)
    for u, v in edges:
        d.add_edge(u, V + v, 1)
    matching = d.max_flow(s, t)
    return V - matching

def project_selection(profits, prereqs):
    n = len(profits); s, t = n, n + 1
    d = Dinic(n + 2)
    INF = 1 << 60
    total_pos = 0
    for p, w in enumerate(profits):
        if w > 0:
            d.add_edge(s, p, w); total_pos += w
        elif w < 0:
            d.add_edge(p, t, -w)
    for p, q in prereqs:           # picking p requires q
        d.add_edge(p, q, INF)
    return total_pos - d.max_flow(s, t)


# profits=[3, -1, -2], prereqs=[(0,1),(0,2)]:
# pick project 0 (+3) requires 1 (-1) and 2 (-2) -> net 0; or pick nothing -> 0

def segment(n, m, a, b, neighbors):
    # a[i], b[i] indexed by pixel id = r*m + c; neighbors: list of (i, j, penalty)
    N = n * m; s, t = N, N + 1
    d = Dinic(N + 2)
    for i in range(N):
        if a[i] > 0: d.add_edge(s, i, a[i])
        if b[i] > 0: d.add_edge(i, t, b[i])
    for i, j, w in neighbors:
        d.add_edge(i, j, w); d.add_edge(j, i, w)
    cut_value = d.max_flow(s, t)
    # label: reachable from s in residual = foreground
    seen = [False]*d.n; stack=[s]; seen[s]=True
    while stack:
        u = stack.pop()
        for e in d.head[u]:
            if d.cap[e] > 0 and not seen[d.to[e]]:
                seen[d.to[e]] = True; stack.append(d.to[e])
    foreground = [i for i in range(N) if seen[i]]
    return cut_value, foreground