Hey guys, I've been trying to solve 1076 in Timus and I'm familiar it can be done with Hungarian algorithm or using flows, but can someone explain to me or give me a link(in English preferably) for Hungarian algorithm with O(n^3) complexity. And also, can someone tell me how to transform this problem to a flow problem. I would be very thankful if there is any response :)

http://translate.google.com/translate?sl=auto&tl=en&js=n&prev=_t&hl=en&ie=UTF-8&eotf=1&u=http%3A%2F%2Fe-maxx.ru%2Falgo%2Fassignment_hungary (I think so !)

Sometimes translation is very poor, for example, "Description of wood pieces in the base case". "wood" should be translated as "tree" :)

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm

connect

W_{i}to source,J_{j}to the sink if you want to solve it using min cost max flowCan you explain which is Wi and which is Jj and what should be the flow and the cost of each edge. Thanks for the TopCoder link. I haven't noticed they have a tutorial about that :)

given

Nworkers (W_{i}) andMjobs (J_{j}),c_{ij}— cost of i-th worker to perform j-th job. Let's build a bipartite graph as described in this article and add source and sink.costs:

c_{ij}for edges connectingW_{i}andJ_{j}and 0 for the rest.max capacities: 1 for all edges.

f_{ij}— flow on edge (i,j) provided by min cost max flow algorithm. It can be either 0 or 1;f_{ij}= 1 means i-th worker have to perform j-th job.Answer will be equal to