#NEWLINE# def kuhn_munkres( G ) : #NEWLINE# #INDENT# 'Maximal profit perfect matching\n\n    for minimum cost perfect matching just inverse the weights\n\n    :param G: squared weight matrix of a complete bipartite graph\n    :complexity: :math:`O(n^4)`\n    ' #NEWLINE# assert ( len ( G ) == len ( G [ 0 ] ) ) #NEWLINE# n = len ( G ) #NEWLINE# mu = ( [ None ] * n ) #NEWLINE# mv = ( [ None ] * n ) #NEWLINE# lu = [ max ( row ) for row in G ] #NEWLINE# lv = ( [ 0 ] * n ) #NEWLINE# for u0 in range ( n ) : #NEWLINE# #INDENT# if ( mu [ u0 ] is None ) : #NEWLINE# #INDENT# while True : #NEWLINE# #INDENT# au = ( [ False ] * n ) #NEWLINE# av = ( [ False ] * n ) #NEWLINE# if improve_matching ( G , u0 , mu , mv , au , av , lu , lv ) : #NEWLINE# #INDENT# break #NEWLINE# #UNINDENT# improve_labels ( G , au , av , lu , lv ) #NEWLINE# #UNINDENT# #UNINDENT# #UNINDENT# return ( mu , ( sum ( lu ) + sum ( lv ) ) )