There are n animals who are sick and need to see a doctor. Each animal belongs t

Question

There are n animals who are sick and need to see a doctor. Each
animal belongs to some species: for example, there are some horses, some
dogs, some cats, some goats, etc. Each animal ai must be seen for a total of
hi hours: for example, one animal might need 10 1-hour visits, while another
animal just has a cold and only needs to be seen for 1 1-hour visit. It is ok
to split this time between as many doctors as you need: for instance, for the
first animal, one doctor might do 1 1-hour visit, another might do 7.5 1-hour
visits, and a third may do 1.5 1-hour visits.
There are m doctors, and each doctor is able to treat certain species of animals, but not necessarily all (for example, some doctors might be able to
treat dogs and cats, but not horses, goats, or elephants). Additionally, each
doctor Dj has a cap Cj on the total number of hours that she is able to work.
Assume all hi and Cj values are positive integers. Your goal is to determine
how to assign doctors to animals so that each animal is seen for the required
number of hours.
Design an algorithm to solve this problem by using network
flows. Be pre-cise about the structure of the graph. It is sufficient to explain how to create
the graph, and then say to apply the existing network flow algorithm to the
graph.

Explanation / Answer

Solution:

The flow network design:

Algorithm:

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.