A while ago I decided to learn about Hungarian algorithm. After watching some videos and reading some articles I think I got the main idea:
1) Find the minimum number in each row and subtract it from all elements in the row.
2) Find the minimum number in each column and subtract it from all elements in the column.
3) Cover all zeroes with minimum number of vertical and/or horizontal lines.
4) If the number of the lines is N, then we have found our assignment. Otherwise, find the minimum uncovered number, subtract it from all uncovered numbers and then go back to step 3.
Well, the thing is that I never found a good implementation. I can implement step 1 and 2. For step 3, I think that we can check whether the minimum number of lines is equal to N using bipartite matching. But if the minimum number is less than N, I don't know how I can find those covering lines. Please, help me with implementing it.
Thanks in advance!