Let's say I have a population that is scattered and unmoving in a set area with water sources. Each water source has an access range and could overlap with other sources. I have to allocate each source to each person in such a way as to not overload each water source with too many people (let's say max n amount of people per source). Each person can only have one source. How do I maximize coverage, including the possibility that some may not have access due to overloading?

You have each person's potential water sources.

CodePudding user response：

This answer use graph theory. Here's an introduction

This is a max flow problem :

• make a vertex p_i for each person
• make a vertex w_j for each water source
• make a source vertex S and a sink vertex T
• make an edge from the source to each person p_i, with capacity 1 (each person can have only one water source)
• for each person p_i, make an edge to each water source w_j if this person is in range of the water source
• for each water source w_j, make an edge to the sink with capacity equal to the maximum of people this source can have.

Then solve maximum flow. As the water source only have an "out" capacity of n, there can only be "n" people connected to that source.

If people are grouped into communities, you can go faster by grouping them, but you have to make the edge from S to the community with a capacity of the population of the community.