Что я должен использовать для реализации взвешенного двухпартийного алгоритма соответствия в C++?

Question

У меня есть проект, он просит меня распространять курсы для студентов. Все студенты спрашивают о некоторых курсах, но им разрешено получать только некоторое количество из них (это может быть то, что они требуют, меньше или просто 0), все курсы имеют квоты, и мне нужно выяснить, существует ли идеальное совпадение (все квоты заполнены и учащиеся получают то, что им разрешено), - если существует выход этого соответствия.

Я только что получил вход и сохранил его в объектах до сих пор. В проекте есть ограничение по времени, чего я не знаю, где начать. Все предложения или метод для этого проекта?

Я думаю, что я должен реализовать двунаправленный алгоритм сопоставления. Я новичок в C++, поэтому мне нужно реализовать как класс узла, так и класс edge? Или я должен использовать список смежности? Какой из них быстрее работает?

Например, студент запрашивает уроки, пронумерованные 3,4 и 5, но ему разрешено брать 2 урока, поэтому алгоритм должен дать 2 из этих вариантов, если есть идеальная возможность сопоставления.

То, что я представлял по двухсторонней проблеме, было таким, но я думаю, что это трудно реализовать. http://i.stack.imgur.com/wtJ6o.jpg

1.student wants 3 ,4 system allows him to take 2 lessons 
2.student wants 1,2,3,4 system allows him to take 3 lessons 
3.student wants 1,2,3,4 system allows him to take 2 lessons 
4.student wants 1,3,5 system allows him to take 2 lessons 
5.student wants 2,5 system allows him to take 1 lessons 

1.lesson's quota = 2 
2.lesson's quota = 1 
3.lesson's quota = 2 
4.lesson's quota = 3 
5.lesson's quota = 2 

I just wrote this ,this might not be the best example. 
One possible solution is = 1 -> (3,4) 2->(1,2,4) 3->(3,4) 4->(1,5) 5->(5) 
Another is = 1 -> (3,4) 2->(1,2,4) 3->(1,4) 4->(3,5) 5->(5) 

там может быть больше, я не знаю.

(студент -> уроки)

Answer 1

Поскольку один студент может быть назначено более одного курса, я не думаю, что проблема может быть решена с помощью простого алгоритма максимального двудольного соответствия.

Эта проблема представляет собой тип transportation problem, где курсы sources, а учащиеся - destinations. Квота каждого курса - это capacity, demand для каждого ученика - это количество уроков, которые система позволяет ему.

EDIT:

Вы можете сформулировать транспортную проблему следующими изменениями:

Сплит уроки таким образом, что каждый урок имеет котировку 1. Таким образом, в вашем примере случае должно быть 10 уроков. Назначьте расходы следующим образом:

Demand: 2 3 2 2 1 
     St1 St2 St3 St4 St5 
Less1.1 5 0 0 0 5 
Less1.2 5 1 1 1 5 // cost for second dummy lesson is slightly high to differentiate. 
Less2.1 5 0 0 5 0 
Less3.1 0 0 0 0 5 
Less3.2 1 1 1 1 5 
Less4.1 0 0 0 5 5 
Less4.2 1 1 1 5 5 
Less4.3 2 2 2 5 5 
Less5.1 5 5 5 0 0 
Less5.2 5 5 5 1 1