So I've recently started looking into network flows (Max flow, min cuts, etc) and the general problems for network flow always involve assigning "n" of something to "k" of another thing. For example, how would I set up a network flow for "n" children in a city that has "k" schools such that the children's homes are within x kilometres of the school (for simplicity, let's just say 1km)?
What if I were to further add limitations, for example, say each school cannot have more than 100 students? Or 300 students? Could someone help me with how I would initially set up my algorithm to approach problems like these (would appreciate any references too)? They tend to show up on past midterms/exams, so I just wanted to be prepared
Create vertices for each student and each school. Draw an edge with capacity 1 from each student to each school that they can attend according to your distance constraint. Create a source vertex with edges to each student with a capacity of 1. Create a sink vertex with edges coming in from each school with capacities equal to each school's maximum capacity.
Running a standard max-flow algorithm will match as many students as possible to schools. Not every student is guaranteed to get to go to school, of course, given the constraints.
This is basically a modification of the standard maximum bipartite matching algorithm. The main difference is that the sinks have capacities greater than 1, which allows multiple students to be matched to a school.