判断能否按学生偏好分配至对应容量班级的算法及实现

这个属于带容量限制的二分图匹配场景，最优解法是最大流建模，具体建模逻辑如下：

• 构建4层流网络节点：
  1. 1个源点，作为流的起始节点
  2. N个学生节点，每个节点对应一名学生
  3. K个班级节点，每个节点对应一个班级
  4. 1个汇点，作为流的结束节点
• 按如下规则给节点连边：
  • 源点到每个学生节点连容量为1的边：保证每名学生仅被分配1次
  • 学生节点到自己的所有意向班级节点连容量为1的边：保证学生仅能被分到意向班级
  • 每个班级节点到汇点连容量为对应班级容纳上限的边：保证班级人数不超过容量限制
• 计算源点到汇点的最大流：如果最大流值等于学生总数N，说明所有学生都可以被分配到意向班级，输出YES，否则输出NO。

该模型下采用Edmonds-Karp算法求最大流的时间复杂度为O(N*(N+K))，对于大部分竞赛场景的输入规模都能轻松通过。

你提供的基于Ford-Fulkerson（BFS实现即Edmonds-Karp算法）的代码思路是正确的，但存在可优化的点：

• 原实现中将每个班级拆成了和容量相等的子节点，本质是手动模拟班级到汇点的容量限制，无需拆分节点，直接给班级到汇点的边设置对应容量即可，可大幅减少节点数，提升运行效率。
• 代码中存在两处冗余/笔误：
  1. 学生连意向班级的边时重复赋值了两次边容量，可删除多余的一行赋值语句
  2. 示例输入中preference数组长度为5，和N=4不符，属于输入笔误，实际使用时需保证两者长度一致。

内容的提问来源于stack exchange，提问作者Mukesh Ranjan