Given a bipartite graph with nonnegative edge weights, find a matching with maximum total weight (maximum number of edges is not required).

Example:

V = {1, 2, 3, 4}, E = {{1, 2}, {3, 4}, {2, 3}}

w({1, 2}) = 1, w({3, 4}) = 1, w({2, 3}) = 10

Optimal solution: {{2, 3}}

A friend suggested the following solution:

1. Ignore weights and find maximum cardinality bipartite matching MCBM.
2. For each , define w'(e) = BIGVALUE - w(e).
3. Find mincost flow for f = 1, 2, 3, ..., MCBM with respect to new weight function w'. Output the minimum.

Will that work? Is there any faster solution?