algorithm - 解决问题_使用最大流

Question

我正在尝试解决这个问题 Problem .

问题陈述如下

伟大的 Charzeh 正在与 Joffrey Baratheon 玩游戏。有n七个王国的骑士。 i-th骑士的力量等于ai (0 ≤ ai < m) .还有n+m-1 numbers f0, f1, ..., fn+m-2在黑色城堡的墙壁上。

“游戏”包括两个回合。在第一轮中，Charzeh 选择数字排列 0, 1, ..., n-1 like p0, p1, ..., pn-1 .

在第二轮中，乔佛里选择整数 i (0 ≤ i < n)然后斩首fpi + ai临冬城的随机居民。 Charzeh 很善良，而 Joffrey 很残忍。这就是为什么 Charzeh 试图最小化而 Joffrey 试图最大化被斩首的人数。

如果他们都打得最好，会死多少人？

对于输入:

7 0 9 1
5 61 53 6 7 72 75 42 5 79 91 5 16

答案是7

当我浏览社论时，它显示可以使用最大最小流量来解决。我不知道这个算法在这里是如何工作的。任何人都可以向我解释如何解决这个问题，即让我了解这个算法在这里是如何工作的。

Answer 1

唯一重要的值是 max(fpi + ai) .所以真正的问题是最小值是多少 X这样至少有一个排列 fpi + ai <= X对于 i 的所有值。

要检查是否存在这样的排列，您可以创建二分图。一方面，您的节点对应于 f 的位置，另一方面，您的节点对应于 a 的值.你在 f[x] 之间有优势和 a[y]比较 f[x] + a[y] <= X ，也就是说，如果你配对 f[x] 的排列和 a[y]适用于解决方案。所有权重都应为 1。您现在可以计算结果图中的最大流量。如果您能够插入 n 个单位的流量(连接您拥有的所有 n 个节点)，那么这是一个满足初始条件(fpi + ai <= X)的排列。

所以现在您所要做的就是对最小值 X 进行二分查找。您仍然可以在相应的图中找到 n 个单位的流量。如果我没记错的话，复杂度将是 O(log(N+M)*N^3)日志来自二进制搜索和 N^3来自流算法。

您还可以尝试使用这样一个事实，即当您增加 X 时相应的图严格来说是原始图的超集(您不会通过增加 X 来删除边)。这意味着您目前为 X 的较低值找到的部分解决方案是计算 X 的增加值的流量的合理起点。另一种方式也有效，但它更加困惑(您需要找到边缘使用不再满足条件并在图中找到替代连接)。但是除非你需要榨取每一点性能，否则我不会为额外的复杂性而烦恼。