I am trying to reduce my problem to a max flow problem so I can run the max flow algorithm on this problem. But there are some things that I am missing while transforming my problem.
My problem is:
And the goal is:
If I put students and classes as vertices (please see image above), then put a source node
s that has an edge to each student and a sink node
t that has an edge to each classes, what will be the edge costs?
Are the following assumptions correct?
I think the edge between students and classes cost should be 1. Because a student can only enroll once to a class in a term. I think edge cost between classes and the sink node
t will be the maximum capacity of a class.
I don't have an idea about edge costs between source node
s and students nodes.
And at the end, after arranging, do we just need to run max flow algorithm?
I think that a max flow from S to any student of 5, and max flow of capacity from each class to T and 1 from each student to each class would satisfy your requirements. BTW, that is not an edge cost but rather an edge flow capacity.
What if we add an addition requirement: There are 5 periods, each student can only take one class per period classes are, instead of all day, in a certain period