Solve multiple-source multiple-destination graph game

Question

I'm trying to categorize the graph problem below or find hints to its solution.

There is an (adjacency) matrix that can contain 3 types of elements: units, points and simple terrain.

Terrain has no specific meaning.

Units have a position (x,y defined by the matrix) and a number of points that they can acquire.
Points have a position (x,y defined by the matrix).
The cost of acquiring a point is the Manhattan distance between a point and unit.
Each point can only be acquired by one unit.

The problem is: how to find the minimal cost configuration of units acquiring points, such that all resources of the units are depleted?

Example:
u1 can acquire 3 points
u2 can acquire 2 points

p1 n n p2  
n u1 n p3  
p4 n n n  
n n u2 p5

One of the optimal solutions is:

u1 = p1, p2, p4  
cost(u1)=2+3+2=7  
u2 = p3, p5  
cost(u2)=3+1=4  
Total cost = 11  

(minimal for this configuration)

Notes: I have tried solving this with uniform cost search and A*(with a simple heuristic), but even for small sizes of the matrix, I get a very high number of states and run out of memory.

Answer 1

I can reduce it to min-cost-max-flow problem.

Let's make a network. Assign a vertex to each unit and each point. For each pair (unit, point) add an oriented edge with capacity 1 and cost equal to corresponding Manhattan distance. Add a sink, connect it to all units. Add a trap and connect all points to it.

Assign the following values of cost and capacity:
cap( u, v ) = 1, if there is an edge from u to v
cost( u, v ) = 0, if u = sink or v = trap; otherwise it's equal to manhattan distance from unit u to point v.

Now if we find min-cost-max-flow in this network, it will be the solution to your problem. Why ? Because we found the minimal cost way to move a unit of flow from each "unit" vertex to some "point" vertex, which is equivalent to the original problem.