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 |