影响米学生n组？ [英] Affect m students to n groups?
问题描述
我想影响学生的M组（M〜20）为n项目（N〜6）。还有一个额外的约束：我只能beetween p影响（P〜4）Q（Q〜6）组，每个项目
I'd like to affect m groups (m ~ 20) of students to n projects (n ~ 6). There is an additional constraint : I can only affect beetween p (p ~ 4) to q (q ~ 6) groups to each project.
每个组都有从它最喜欢的最坏的一个数量级的项目。
Each group has to order the projects from the one it likes most to the worst.
我读过，我可以使用匈牙利算法如果m = n和我应该使用福特Fulkerson算法或埃德蒙兹 - 卡普算法< /一>在一般情况下
I've read I could use the Hungarian algorithm if m = n and I should use the Ford-Fulkerson algorithm or the Edmonds–Karp algorithm in the general case.
能否请你帮我辨别将图形是在我的情况是什么？我想节点组和项目，且边缘有由组的方式像项目确定的成本。但是，什么是能力属性？和如何尊重我的原始约束？
Could you please help me to discern what will the graph be in my case ? I guess nodes are groups and projects, and edges have a cost determined by the way groups like projects. But what is the capacity property ? And how to respect my original constraint ?
推荐答案
图表看起来应该是这样的：
The graph should look this way:
-
源节点。
The source node.
汇聚节点。
第一组节点。这些节点对应于学生组（每个组中的一个节点）。应该有从源节点从该组中的每个节点的边与容量= 1 （我假设每个组只能做项目）和成本= 0 。
The first set of nodes. These nodes correspond to groups of students(one node for each group). There should be an edge from the source node to each node from this set with capacity = 1(I assume that each group can do only project) and cost = 0.
第二组节点。这些节点对应于项目。应该有从该组到宿节点的每个节点与成本= 0 和容量=基团的最大数量被允许，一个边缘做这个项目。
The second set of nodes. These nodes correspond to projects. There should be an edge from each node from this group to the sink node with cost = 0 and capacity = the maximum number of groups that are allowed to do this project.
应该是从第一组从第二组的每个节点的每个节点容量= 1 和成本边缘= - 如何多的这组喜欢这个项目（ - 是当且仅当这个数字是更大的必要，更这群喜欢这个项目）。
There should be an edge from each node from the first set to each node from the second set with capacity = 1 and cost = -how much this group likes this project(- is necessary if and only if the bigger this number is, the more this group likes this project).
现在我们必须找到一个从源到接收节点的最小成本最大流量。
Now we have to find the minimum cost maximum flow from the source to the sink node.
这篇关于影响米学生n组？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
