Statistically, the arrival of spring typically results in increased accidents and increased need for emergency medical treatment, which often requires blood transfusions. Consider the problem faced by a hospital that is trying to evaluate whether its blood supply is sufficient. The basic rule for blood donation is the following. A person’s own blood supply has certain antigens present (we can think of antigens as a kind of molecular signature); and a person cannot receive blood with a particular antigen if their own blood does not have this antigen present.
Concretely, this principle underpins the division of blood into four types:A, B, AB, and O. Blood of type A has the A antigen, blood of type B has the B antigen, blood of type AB has both, and blood of type O has neither. Thus, patients with type A can receive only blood types A or O in a transfusion, patients with type B can receive only B or O, patients with type O can receive only O, and patients with type AB can receive any of the four types.4
(a) Let sO, sA, sB, and sAB denote the supply in whole units of the different blood types on hand. Assume that the hospital knows the projected demand for each blood type dO, dA, dB, and dAB for the coming week.
Give a polynomial-time algorithm to evaluate if the blood on hand would suffice for the projected need.
This problem needs to be solved with network flow problem. As part of your solution, you should draw a flow network. You should also discuss the eciency of your algorithm, i. e. say what the eciency class is and why. blood type supply demand
a. O 50 45
b. A 36 42
c. B 11 10
d. AB 8 3