Pagini recente » Cod sursa (job #1009782) | Cod sursa (job #2664162) | Cod sursa (job #2156441) | Cod sursa (job #343094) | Cod sursa (job #3190716)
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()