Min s-t cut in a network

I believe that you can solve this problem by finding a minimum cut in a graph with slightly modified constraints. The idea is as follows - since the cost of a cut is equal to the total capacity crossing the cut, we could try modifying the graph by adding in an extra edge from each node in the graph to t that has capacity one. Intuitively, this would mean that every node in the same part of the cut as s would contribute one extra cost to the total cost of the cut, because the edge from that node to t would cross the edge. Of course, this would definitely mess up the actual min-cut because of the extra capacity. To fix this, we apply the following transformation - first, multiply the capacities of the edges by n, where n is the number of nodes in the graph. Then add one to each edge. The intuition here is that by multiplying the edge capacities by n, we've made it so that the cost of the min-cut (ignoring the new edges from each node to t) will be n times the original cost of the cut. When we then add in the extra one-capacity edges from each node to t, the maximum possible contribution these edges can make to the cost of the cut is n - 1 (if every node in the graph except for t is on the same side as s). Thus the cost of the old min-cut was C, the cost of the new min-cut (S, V - S) is nC + |S|, where |S| is the the number of nodes on the same side of the cut as s.

More formally, the construction is as follows. Given a directed, capacitated graph G and a (source, sink) pair (s, t), construct the graph G' by doing the following:

1. For each edge (u, v) in the graph, multiply its capacity by n.
2. For each node v in the graph, add a new edge (v, t) with capacity 1.
3. Compute a min s-t cut in the graph.

I claim that a min s-t cut in the graph G' corresponds to a min s-t cut in graph G with the fewest number of nodes on the same side of the cut as s. The proof is as follows. Let (S, V - S) be a min s-t cut in G'

tl;dr Compute an max s-t flow and let S be the set of nodes reachable from s by arcs of positive residual capacity.

Proof of correctness: clearly S is an min s-t cut (cut = set of nodes in the part containing s). Suppose that S* is an s-t cut smaller than S (i.e., |S*| < |S|). By an easy counting argument, let u be a node in S - S*. If we add a positive capacity arc from u to t, then the computed flow has an augmenting path and is no longer maximum, but the capacity of the cut S* is unchanged, since u and t both belong to V - S*. We conclude by weak duality that S* is not a min cut.

In fact, the class of s-t min cuts is a distributive lattice under intersection and union, so every instance of your problem has a unique solution.