Waif Until Dark

This problem asks you to find a maximal matching in a bipartite graph where there are restrictions on the number of items that can match from certain subsets on one half of the graph.

The classic bipartite matching is maxflow, with a supernode on each side and a limit of 1 to each of the real nodes. This problem is a simple extension where the "left" (toy) side of the graph has another layer of nodes which represent classes of toys. the flow from the supernode to each "class of toy" node is specified in the input, and the flow to each toy is 1. Then flow from toys to all children to children who like that toy of capacity 1, and flow from children to super-sink-node of capacity 1.

Runtime of maxflow is somewhat hard to calculate, but we know the solution is <100, because that's the max children. That means we need to BFS through the graph at most 100 times. The graph only has n^2 edges in it (if each child is paired with each toy). Which makes the runtime fast enough.