Use a max flow algorithm to solve the following problem. Elbonia is grappling with a COVID outbreak. It has N affected cities 1,…,N. City i has p(i) many patients who require an intensive care bed. Hospitals in a city i have b(i) many available intensive care beds in total. Transportation of patients living in a city i to a hospital in a city j where they will be treated is possible only if the city j is within K kilometers (by road) from city i. You are given the above numbers and a map of Elbonia with road distances and have to design an algorithm which assigns each patient from every city i to a sufficiently close city j which has a hospital where that patient can be treated. Your algorithm should make sure that no city i has to accommodate more patients than its total intensive care unit capacity b(i). It should also output a message “impossible” if there is no such assignment. In particular:
(a) describe what the vertices of the flow graph are;
(b) describe what the edges of the flow graph are;
(c) describe how the capacities of all edges are assigned;
(d) after applying a max flow algorithm describe how the patients are assigned to cities where they will be treated;
(e) describe how it is determined that the problem has no solution meeting the constraints given.
Note: p(i) can be larger or smaller or equal to b(i); also a patient from a city c(i) does NOT have to be treated in a hospital in the same city.