Construct bipartite graph After this observation we find whichever perfect matching in Thus our problem has been transformed to the following equivalent: in an oriented graph with weight of vertices find subset S of the vertices with minimum sum of weights and without outgoing edge with other end not in S. This problem is known to be equivalent to finding minimum cut Assign to the edges of |

in fact what I did was sum the outgoing weights from s after computing max flow in the graph; I was able to prove this is the required number"you meant that you substract this from the result you obtained of the max flow, that seems to work, but could someone explain me why?