Q:

assignment prob flow network solution

I have an assignment problem with cost matrix C, eg:
21 30 26 16 20
27 29 28 20 38
39 25 21 19 23
28 24 30 29 16
30 33 32 17 31
where C[i][j] means cost for worker i to do job j.
How can I solve this with a network flow algorithm? I would welcome any hints.

A:

In case you are still looking for a solution, you can solve this as a Minimum-cost flow problem:

Create a source node connected to your N workers by edges with
capacity 1 and cost 0
Connect each worker i to each job j by edges of capacity 1 and cost C[i][j]
Finally connect each job to a sink node with edges of capacity 1 and cost 0

Your problem is equivalent to minimizing the cost of pushing N flow units through the network from source to sink.

