حل تمرین بازرگانی سوکرات و پسران کوئرا با پایتون

4
9 2 7 8
6 4 3 7
5 8 1 8
7 6 9 4

1
0
2
3

import sys

input = sys.stdin.read
data = input().split()
n = int(data[0])
cost = []
index = 1
for i in range(n):
    row = []
    for j in range(n):
        row.append(int(data[index]))
        index += 1
    cost.append(row)

u = [0] * n
v = [0] * n
p = [-1] * n
way = [-1] * n

for i in range(n):
    links = [-1] * n
    mins = [float('inf')] * n
    visited = [False] * n
    marked_i = i
    marked_j = -1
    j = 0
    while True:
        j = -1
        for j1 in range(n):
            if not visited[j1]:
                cur = cost[marked_i][j1] - u[marked_i] - v[j1]
                if cur < mins[j1]:
                    mins[j1] = cur
                    links[j1] = marked_j
                if j == -1 or mins[j1] < mins[j]:
                    j = j1
        delta = mins[j]
        for j1 in range(n):
            if visited[j1]:
                u[p[j1]] += delta
                v[j1] -= delta
            else:
                mins[j1] -= delta
        u[i] += delta
        visited[j] = True
        marked_j = j
        marked_i = p[marked_j]
        if marked_i == -1:
            break
    while True:
        if links[j] != -1:
            p[j] = p[links[j]]
            j = links[j]
        else:
            break
    p[j] = i

assignment = [-1] * n
for j in range(n):
    assignment[p[j]] = j

for i in range(n):
    print(assignment[i])