Problem: You sell $k$ items and have each item $1\leq j \leq k$ exactly $s_j$ times at stock. There are $n$ customers, each of which has a list of items the customer wants. I should answer the question whether it is possible that every customer gets some item from its list and model this as a max flow problem.
Solution: My network looks as follows: I have a source edge with no particular meaning, then a layer of $k$ vertices representing the items whereby there is an edge from the source to item $j$ with capacity $s_j$. Then, a second layer of $n$ vertices representing the customers and there is an edge from dish $j$ to some customer vertex with capacity 1 if the item is on the customers list. Lastly I have from each customer an edge with capacity one to the sink vertex. Does this network description sound correct so that it solves the problem by finding the max flow (if it exists)?
Best Answer
Yes, your network model is completely correct! Now you can try to calculate the maximum Flow through the network and if it equals the number of clients, it is possible to give every customer at least one of the items on his list.