Solving project selection with a network flow algorithm I am currently studying network flow algorithms and one of its application is supposed to be "Project Selection". A (more) complete description is given here, but the problem basically is this:
There is a graph $G$ with a number of projects $P$ as nodes. Projects have a revenue $p_i$ and a dependency from project $j$ on $i$ is given as an edge $(j,i)$.
Now it is said that the minimum cut will provide the most efficient set of projects to take if makes a source node $s$, sink node $t$ and make an edge $(s,i)$ if $p_i > 0$ and an edge $(i,t)$ if $p_i < 0$
There are however several cases I can think of that seem impossible to solve in this matter.
Consider for example a case with only 1 project ($P = {a}$) with a revenue of +10. Clearly the most profitable set of projects to do is ${a}$, but a flow is impossible in this case (and thus all possible cuts are minimal, including those without $a$).

Or if there is a project with no cost, it will not have a connection with the source nor sink and as such does not have to be in the minimum cut.
(pic coming later)
(other counter-examples I can think of basically are all based on these 2 problems)
Can anyone shed some light on this algorithm for me?
 A: I hesitate to write this up as an answer, but I guess I don't have the 'comment' privilege yet.
These types of issues are important to understand, as they force you to understand the problem in more depth and come up with a model that accurately describes it without too much fluff.
Anytime you encounter a case that breaks your model, you can try to add something to the model that allows you to model it accurately.
The one project case is obvious: there's no problem to solve.  You either do the project or you don't.
A project with zero cost almost makes no sense.  If the cost is zero, then I'd try to change the model to more accurately describe the problem.  In the simplest case, a business choosing projects to tackle would have at least two costs in mind: time spent, money spent.
Now, suppose project X1.0 (v1.0) is already complete, but it sucks.  The choice is one of:


*

*X1.0 -> Y1.0 (Just use it and put up with the headaches)

*X1.1 -> Y1.0 (Improve X1.0)

*X2.0 -> Y1.0 (Re-write it)


The cost of traversing the edge from X to Y in (1) is zero.  However, a proper model for this would have 3 nodes in the graph for Y: one for each path.  Treating Y as a single node with separate edges then creates the implicit assumption that the path from Y1.0 to Z1.0 is the same no matter which of the 3 options you pick.
In short: this is what mathematical modeling is all about.  Analyzing the problem and coming up with a good way to accurately model it.  If something breaks it, more than likely it's your model.
A: You misunderstood the result. Whether a flow is possible or not is not relevant.  In your first case, where the graph is 
$ s \to a  \,  \ t $
the minimal cut (=partition of the nodes into two sets, one containing s and the other t) is ({s,a}, {t}) which has capacity 0 because there are no edges from one set to the other.  The other cut ({s},{a,t}) has capacity 10 (the capacity of the edge from s to a).  In the other example with revenue 0, both possible cuts have capacity 0 so you can either do project a or not; both are optimal.
