Двустороннее сопоставление с ограничениями
При самостоятельном изучении заметки Джеффа Эриксона о приложениях maxflow доступны здесь
http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/23-maxflowapps.pdf
Я столкнулся с этой проблемой, которая поставила меня в тупик
Сенат факультета решил созвать комитет, чтобы определить, должен ли вождь Иллинивек стать официальным символом талисмана Глобального кампуса Университета Иллинойса. Точно один преподавательский состав должен быть выбран из каждого академического отдела для работы в этом комитете.
У некоторых преподавателей есть назначения в нескольких отделах, но каждый член комитета будет представлять только один отдел.
Например, если профессор Благоевич связан как с Департаментом коррупции, так и с Департаментом глупости, и он выбран в качестве представителя глупости, то кто-то другой должен представлять коррупцию.
Наконец, университетская политика требует, чтобы любой комитет по символам виртуальных талисманов содержал одинаковое количество доцентов, доцентов и полных профессоров. К счастью, число отделов кратно 3. Опишите эффективный алгоритм выбора членов Глобального комитета по делам иллиниевок. Ваш вклад представляет собой список всех преподавателей, их званий (ассистент, ассоциированный или полный), а также их ведомственной принадлежности. Есть n преподавателей и 3k кафедр.
Это похоже на проблему двудольного типа, когда мы хотим назначить преподавателей комитету.
Но ограничения сбивают меня с толку. Как построить график (выбрать узлы и мощности), чтобы я мог применить maxflow ford-fulkerson для поиска совместимого назначения?