OJ Board

hi,

i want to use hungarian method, KUHN-MUNKRES algorithm for assignment problem which is well-known.


as i searched in google, ways of algorithm are following:
also, total time complexity of this algorithm is o(n^3)

N is matrix size (matrix is N*N)
1. subtract min values in each rows and cols. o(n^2)
2. find minimum number of lines, which cover all zeros in matrix
3. if the number of found lines (which cover zeros) is equal to N
then exit the algorithm
4. otherwise, find minimum values not covered by lines founded step 3,
let it K, then subtract all elements in matrix by K
and add covered element by K o(n^2)
5. goto step 2



the number of loops step 2-5 is o(n),

so i must do step 2 in o(n^2).


but i don't know how i can find this minimal covers in such time..

please help me. i'm confused.

I've the same problem. Could Anybody explain how to
find minimum number of lines, which cover all zeros in matrix ?

Wojciech

There's a readable description of the algorithm here: http://www.math.uwo.ca/~mdawes/courses/ ... unkres.pdf
It's much simpler to understand that the above one...