Cod sursa(job #2960524)

Utilizator avethegamerAveTheGamer avethegamer Data 4 ianuarie 2023 16:17:42
Problema Taramul Nicaieri Scor 100
Compilator py Status done
Runda Arhiva de probleme Marime 2.21 kb
from collections import defaultdict
from queue import Queue

with open("harta.in", "r") as fin:
    nr_noduri = int(fin.readline())
    start = 0
    end = nr_noduri * 2 + 1
    graph = defaultdict(list)
    capacity = defaultdict(dict)
    parent = [None] * (end + 1)

    for i in range(1, nr_noduri + 1):
        x, y = map(int, fin.readline().split())
        graph[start].append(i)
        graph[i].append(start)
        capacity[start][i] = x
        capacity[i][start] = 0

        graph[nr_noduri + i].append(end)
        graph[end].append(nr_noduri + i)
        capacity[nr_noduri + i][end] = y
        capacity[end][nr_noduri + i] = 0

    for i in range(1, nr_noduri + 1):
        for j in range(1, nr_noduri + 1):
            capacity[i][nr_noduri + j] = 0
            capacity[nr_noduri + j][i] = 0
            if i != j:
                graph[i].append(nr_noduri + j)
                graph[nr_noduri + j].append(i)
                capacity[i][nr_noduri + j] = 1


def bfs():
    vizitat = [False] * (end + 1)
    q = Queue(maxsize=end)
    q.put(start)
    vizitat[start] = True
    parent[start] = -1
    while not q.empty():
        nod = q.get()
        for vecin in graph[nod]:
            if not vizitat[vecin] and capacity[nod][vecin] > 0:
                parent[vecin] = nod
                if vecin == end:
                    return True
                q.put(vecin)
                vizitat[vecin] = True
    return False


def edmonds_karp():
    max_flow = 0
    min_flow = float("inf")
    while bfs():
        x = end
        while x != start:
            tata = parent[x]
            if capacity[tata][x] < min_flow:
                min_flow = capacity[tata][x]
            x = tata
        x = end
        while x != start:
            tata = parent[x]
            capacity[tata][x] -= min_flow
            capacity[x][tata] += min_flow
            x = tata
        max_flow += min_flow

    return max_flow


if __name__ == '__main__':
    with open("harta.out", "w") as fout:
        fout.write(f"{edmonds_karp()}\n")
        for i in range(1, nr_noduri + 1):
            for vecin in graph[i]:
                if vecin != start and capacity[i][vecin] == 0 and vecin != end:
                    fout.write(f"{i} {vecin-nr_noduri}\n")