This problem can be solved with min cut / max flow. There are two main approaches:

Solution 1

Our construction has ~N+M+2~ nodes, representing the source, sink, cities, and roads. The idea is to have edges with capacity ~p~ from the source to the roads, and edges with capacity ~b~ from the cities to the sink. Suppose ~S~ is the set of vertices of a cut including the source. The cost of the cut ~\delta(S)~ is the sum of ~p~ for roads not in ~S~, and ~b~ for cities in ~S~. So, ~S~ corresponds to a choice of cities to pay and roads to profit from.

By adding infinite-capacity edges from the roads to the incident cities, the minimum cut problem now has the constraints that for every profit we profit from, we must pay both incident cities.

So, the answer can be determined after finding the min cut / max flow for this network with ~\mathcal O(N+M)~ nodes and arcs.

Solution 2

Let ~E(S)~ be the set of edges with both ends in ~S~. Then the net profit for a set of vertices ~S~ is ~p(E(S))-b(S)~. However, note the following equation:

$$\displaystyle p(E(S)) = \frac 1 2 \left(\sum_{v \in S} p(\delta(v))-p(\delta(S))\right)$$

So, the answer can be written as

$$\displaystyle \max_{S \subseteq V} \left(-\frac 1 2 p(\delta(S))+\sum_{v \in S} \left(\frac 1 2 p(\delta(v))-b_v\right)\right)$$

Or equivalently, as

$$\displaystyle \min_{S \subseteq V} \left(\frac 1 2 p(\delta(S))+\sum_{v \in S} b'_v\right)$$

where ~b'_v = b_v - \frac 1 2 p(\delta(v))~.

This is very close to a minimum cut problem. To turn it into one, we add a source and sink and add an arc to every node to either the source or sink depending on whether ~b'_v~ is positive or negative.

The resulting flow construction has ~N+2~ nodes and ~\mathcal O(N+M)~ edges.