Cod sursa(job #3190716)

Utilizator z.catincaCatinca Zavoianu z.catinca Data 7 ianuarie 2024 20:48:47
Problema Taramul Nicaieri Scor 20
Compilator py Status done
Runda Arhiva de probleme Marime 1.95 kb
from collections import deque

def bfs(s, d, cap, flux, graf, t):
    deq = deque()
    viz = [0] * (d + 1)

    t.clear()
    t.extend([0] * (d + 1))

    deq.append(s)
    viz[s] = 1

    while deq:
        nod = deq.popleft()
        if nod == d:
            break
        for vec in graf[nod]:
            if not viz[vec] and cap[nod][vec] - flux[nod][vec] > 0:
                deq.append(vec)
                t[vec] = nod
                viz[vec] = 1

    return 1 if t[d] != 0 else 0

def edmond_karp(s, d, cap, flux, graf):
    flow = 0
    mn = 0
    t = []

    while bfs(s, d, cap, flux, graf, t):
        mn = float('inf')
        i = d
        while i != 0:
            if cap[t[i]][i] - flux[t[i]][i] < mn:
                mn = cap[t[i]][i] - flux[t[i]][i]
            i = t[i]

        i = d
        while i != 0:
            flux[t[i]][i] += mn
            flux[i][t[i]] -= mn
            i = t[i]

        flow += mn

    return flow

def main():
    with open("harta.in", "r") as fin, open("harta.out", "w") as fout:
        n = int(fin.readline().strip())
        s = 0
        d = 2 * n + 1

        cap = [[0] * dim for _ in range(dim)]
        flux = [[0] * dim for _ in range(dim)]
        graf = [[] for _ in range(dim)]
        t = []

        for _ in range(1, n + 1):
            x, y = map(int, fin.readline().strip().split())
            k = n + _

            graf[s].append(_)
            graf[k].append(d)
            cap[s][_] = x
            cap[k][d] = y

        for _ in range(1, n + 1):
            for j in range(n + 1, 2 * n + 1):
                if _ != (j - n):
                    graf[_].append(j)
                    graf[j].append(_)
                    cap[_][j] = 1

        fout.write(str(edmond_karp(s, d, cap, flux, graf)) + "\n")

        for i in range(1, n + 1):
            for j in range(n + 1, 2 * n + 1):
                if flux[i][j] == 1:
                    fout.write(f"{i} {j - n}\n")

if __name__ == "__main__":
    dim = 1002
    main()