I have a n*m Matrix filled with non negative integers.

I need to find the maximum sum of the numbers selected such that no two share the same row or column.

What is the best possible solution to it?

I have a n*m Matrix filled with non negative integers.

I need to find the maximum sum of the numbers selected such that no two share the same row or column.

What is the best possible solution to it?

This problem can be solved using Minimum Weight Bipartite Matching. Just take the negative of all numbers.

**Note**: This may not be best way possible as MaxFlow algorithms are slow.

What is the expected time complexity?