find the minimum sum of matrix (n x n) that select only one in each row and column

Question

this is another algorithms problem related to dynamic programming

Here is the problem :

find the minimum sum of the given matrix such that select one in each row and column

For example :

3 4 2

8 9 1

7 9 5

the minimum one : 4 + 1 + 7

I think the solution is network flow (max flow/min cut) but I think it shouldn't be as hard as it is

My solution: seperate to n list[column], column1, column2 ... column n

then start point (S) -> column1 -> column2 -> ... -> column n -> (E) end point and implement max flow/min cut

Answer 1

This is the Assignment Problem which can be considered a special case of minimum weight perfect matching in graphs. The classic way to solve the Assignment Problem is to use the Hungarian Algorithm.