given a N*N matrix … we have to choose N-1 elements elements such that all from diffrent row and diffrent column. and sum of elements are minimized…
any problem releted to this in codechef will also be helpful.or editorial of that problem…
Let’s solve this problem, when we want to choose N elements and minimized their sum.
This should be classic problem. We create graph from this matrix as follows: each row and column represents one vertex. Field in matrix represent edge with value of that field between vertex of its column and row. We can see, that this graph is bipartite. This lead to maximal matching on the graph but with minimum cost.
But I personaly prefer using of bigger hammer: Min cost Max flow algorithm. Just add one source and connect it to all rows and sink connect to all columns. Each vertex has capacity 1.
When we run our McMf algorithm we find maximal flow with minimum value. This means, that each row and each column will be occupied so exactly N edges will be in our flow, each edge (field in original matrix) in different row and column. And their sum will be minimal.
Now we want to choose only N-1 elements. So we can choose, which column won’t contain element, erase this column and run our McMf algorithm on this matrix. This choose exactly N-1 fields with minimal possible sum. Just choose the minimum.
Time complexity of McMf is O(N^4) but we must run it N times, so complexity will be O(N^5).
Sadly I don’t know better approach than this yes. Also it look just like some problems I solve with this approach. But these problems are on local Slovak online judge.
Follow this link
Also see this
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm
This is equivalent to the assignment problem.