2112:Optimal Milking：二分法与最大流快速解决匹配问题

题意：

设有K台挤奶机与C头奶牛，并考虑它们之间的间距情况。要求每头奶牛都需要前往任意一台挤奶机进行服务操作。其中每一台挤奶机最多可服务于M头 奶 牛同时工作。请寻求一种最优配置方案，在此方案下，请确定所有牛奶 Cow都能完成任务时 ，行走路径最长的那一头 Cow 的最小可能路程

思路

显然这是一个二分图匹配问题；其难点在于我们目前仅有一张图。对于其中一些特定的情况而言：
（1）某些牛与机器之间并非直接相连，在此情况下仍可通过间接路径实现连接。
（2）每个机器都配备了一个容量上限。
值得注意的是：
好吧事后诸葛亮，本菜鸟拿到题立马想出了一个绝妙的死路：
先跑一个多源点最短路径算法来计算每头牛到每台机器之间的最短距离。
对于每头牛而言，
将所有可能路径按照长度从小到大排序。
随后开始匈牙利算法进行匹配，
从逻辑上讲这种方法似乎可行，
可惜这种组合可能会导致性能问题。
为了避免这种情况，
我们可以考虑另一种方案：
直接运行网络流算法，
虽然这会带来一定的复杂度提升，
但在当前情况下这是更为可靠的解决方案。

• 怎样构建模型？在解决相关问题时，网络流算法通常被视为核心工具。
  • 应该怎样获得最终结果？对于涉及匹配的问题来说，在运行最大流算法后最多只能确定已配对个体的数量；那么我们又该如何找到离得最近的大牛之间的最短路径呢？
• 接下来我们将集中攻克这两个关键性挑战