Reputation: 1
How to find the maximum flow in a network where a subset of the edges must sum to a given total cost?
Consider the following example:
Given a network containing n nodes describing fuel stations, ℓ nodes for starting points Si (each with k cars), and an endpoint node T, determine the maximum number of valid paths starting from some Si ending at T. Each fuel station contains 1 unit of fuel by default, but we can add pi extra fuel to each station, where the pi sum to p.
If we represent fuel stations as two nodes ('in' and 'out' nodes with a single edge having weight pi in between), we want to maximise flow while ensuring that the pi sum to p.
Note: the problem needs to be solved using a reduction to maximum flow problem.
Tried using auxillary nodes to add 'additional fuel' to each station, but that means the flow represents both fuel and cars, which messes up the algorithm.
Upvotes: 0
Views: 35