Source code online books for professionals by professionals

Doctors on vacation. Kleinberg and Tardos (see “References” in Chapter 1) describe a somewhat similar problem. 
Different objects and constraints, but the idea is somewhat similar still. The problem is assigning doctors to holiday 
days. At least one doctor must be assigned to each holiday day, but there are restrictions on how this can be done. 
First, each doctor is available on only some of the vacation days. Second, each doctor should be assigned to work on 
at most c vacation days in total. Third, each doctor should be assigned to work on only one day during each vacation 
period. Do you see how this can be reduced to maximum flow?
Once again, we have a set of objects with constraints between them. We need at least one node per doctor and 
one per vacation day, in addition to the sink s and the source t. We give each doctor an in-edge from s with a capacity 
c, representing the days that each doctor can work. Now we could start linking the doctors directly to the days, but how 
do we represent the idea of a vacation period? We could add one node for each, but there are individual constraints 
on each doctor for each period, so we’ll need more nodes. Each doctor gets one node per vacation period and an out-
edge to each one. For example, each doctor would have one Christmas node. If we set the capacity on these out-edges 
to 1, the doctors can’t work more than one day in each period. Finally, we link these new period nodes to the days 
when the doctor is available. So if Dr Zoidberg can work only Christmas Eve and Christmas Day during the Christmas 
holiday, we add out-edges from his Christmas node to those two dates.
Finally, each vacation day gets an edge to t. The capacity we set on these depends on whether we want to find 
out how many doctors we can get or whether we want exactly one per vacation day. Either way, finding the maximum 
flow will give us the answer we’re looking for. Just like we extended the previous problem, we could once again take 
preferences into account, by adding costs, for example on the edges from each doctor’s vacation period node to the 
individual vacation days. Then, by finding the min-cost flow, we wouldn’t find only a possible solution, we’d find the 
one that caused the least overall disgruntlement.