java - 应用网络流

Question

所以我最近开始研究网络流量（最大流量、最小切割等），网络流量的一般问题总是涉及将某事物的“n”分配给另一事物的“k”。例如，我如何在一个拥有“k”个学校的城市中为“n”个孩子建立一个网络流，使得孩子们的家在学校的 x 公里范围内（为简单起见，我们只说 1 公里）？

如果我要进一步增加限制，例如每所学校不能有超过 100 名学生怎么办？还是300名学生？有人可以帮助我如何最初设置我的算法来解决这些问题（也希望有任何参考资料）？他们往往会出现在过去的期中考试/考试中，所以我只是想做好准备

Answer 1

为每个学生和每个学校创建顶点。根据您的距离限制，从每个学生到他们可以就读的每所学校绘制一条容量为 1 的边。为每个学生创建一个源顶点，其边的容量为 1。创建一个接收器顶点，其边来自每个学校，其容量等于每个学校的最大容量。

运行标准的最大流量算法将使尽可能多的学生与学校匹配。当然，考虑到这些限制，并不是每个学生都能保证上学。

这基本上是对标准最大二分匹配算法的修改。主要区别在于接收器的容量大于 1，这允许多个学生与一所学校匹配。