def kuhn_munkres(G):      # couplage parfait de profit maximal en O(n^4)
    assert len(G) == len(G[0])
    n = len(G)
    mu = [None] * n                 # couplage vide
    mv = [None] * n
    lu = [max(row) for row in G]    # étiqu. triviaux
    lv = [0] * n
    for u0 in range(n):
        if mu[u0] is None:          # sommet libre
            while True:
                au = [False] * n    # arbre alternant vide
                av = [False] * n
                if improve_matching(G, u0, mu, mv, au, av, lu, lv):
                    break
                improve_labels(G, au, av, lu, lv)
    return (mu,  sum(lu) + sum(lv))
# snip}
Maximal profit perfect matching
dataset/ETHPy150Open jilljenn/tryalgo/tryalgo/kuhn_munkres_n4.py/kuhn_munkres