Max-flow min-cut theorem
Project selection problem

In the project selection problem, there are n projects and m machines. Each project p yields revenue r (p) and each machine q costs c (q) to purchase. Each project requires a number of machines and each machine can be shared by several projects. The problem is to determine which projects and machines should be selected and purchased respectively, so that the profit is maximized.

Let P be the set of projects not selected and Q be the set of machines purchased, then the problem can be formulated as,

Since the first term does not depend on the choice of P and Q, this maximization problem can be formulated as a minimization problem instead, that is,

The above minimization problem can then be formulated as a minimum-cut problem by constructing a network, where the source is connected to the projects with capacity r (p), and the sink is connected by the machines with capacity c (q). An edge (p, q) with infinite capacity is added if project p requires machine q. The s-t cut-set represents the projects and machines in P and Q respectively. By the max-flow min-cut theorem, one can solve the problem as a maximum flow problem.

The figure on the right gives a network formulation of the following project selection problem:

The minimum capacity of an s-t cut is 250 and the sum of the revenue of each project is 450; therefore the maximum profit g is 450 − 250 = 200, by selecting projects p and p.

The idea here is to 'flow' each project's profits through the 'pipes' of its machines. If we cannot fill the pipe from a machine, the machine's return is less than its cost, and the min cut algorithm will find it cheaper to cut the project's profit edge instead of the machine's cost edge.
combination:repeat_prompt, detectable_content:number_placeholders[3], startend:end_checker