应用网络流

Question

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

如果我进一步增加限制，比如每所学校不能超过100名学生呢？还是 300 名学生？有人可以帮助我最初如何设置我的算法来解决这些问题（也将不胜感激任何参考）？他们往往会出现在过去 midterms/exams，所以我只是想做好准备

Answer 1

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

运行 标准的最大流量算法会将尽可能多的学生匹配到学校。当然，考虑到限制条件，并非每个学生都能保证上学。

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