zad1.py

# Ford-Fulkerson + Endomds-Karp

from collections import deque
from checker import check1

def gen_list_and_matrix_from_edges(E): # (u, v, cap)
    n = 0
    for u, v, _ in E:
        u -= 1 # korekcja indeksowania wierzchołków
        v -= 1
        if u > n:
            n = u
        if v > n:
            n = v

    n += 1

    G = [[] for _ in range(n)]
    M = [[0] * n for _ in range(n)]

    for u, v, cap in E: # cap = capacity
        u -= 1
        v -= 1
        G[v].append(u)
        G[u].append(v)
        M[u][v] = cap # sieć residualna

    return G, M, n

def bfs(G, M, s, t, parents, n):
    visited = [False] * n
    Q = deque()

    Q.append(s)
    visited[s] = True

    while len(Q) > 0:
        u = Q.popleft()

        for v in G[u]:
            if M[u][v] and not visited[v]: # jak waga 0 to nie mogę przejść
                Q.append(v)
                visited[v] = True
                parents[v] = u

    return visited[t] # zwraca czy dotarł do t


def edmonds_karp(E):
    G, M, n = gen_list_and_matrix_from_edges(E)
    s, t = 0, n - 1 # w założeniu do zadania
    parents = [None] * n
    inf = float('inf')

    max_flow = 0

    while bfs(G, M, s, t, parents, n): # dopóki da się dotrzeć do t
        bottleneck = inf
        u = t
        while u != s: # przejście od tyłu i wyzanczenie wąskiego gardła ścieżki
            val = M[parents[u]][u]
            if val < bottleneck: bottleneck = val
            u = parents[u]

        max_flow += bottleneck # dla jednej ze ścieżek

        u = t
        while u != s: # powiększenie sieci residentialnej (co uwzględnia też "wycofanie strumienia i przelanie inną krawędzią")
            # znalezienie ścieżki powiększającej
            v = parents[u]
            M[u][v] += bottleneck # sieć residentialna ma wagi dodatnie
            M[v][u] -= bottleneck
            u = parents[u]

    return max_flow


check1(edmonds_karp)