最大流量找到最有利可图的安排

Question

让a_1, ..., a_n演员。每个演员都有一个成本c_1, ..., c_n。另外，我们有投资者，b_1,..., b_m，这样每个投资者都愿意为我们的电影投入q_j资金。一个投资者会把钱投在我们的电影里，如果所有他喜欢的演员，都会出现在我们的电影里。当然，我们可能有多个投资者。寻找行为者/投资者的子集，以使我们的利润最大化(即投资总额减去工资总额)

基本上，解决方案是将一些顶点s连接到每个具有权重q_i边的投资者。接下来，我们将每一位投资者联系起来，让他们更喜欢拥有infinity优势的演员。最后，我们将每个参与者连接到具有权值c_i边的某个顶点c_i。

然后，我们寻找最大流量。

我的问题是：

• 为什么会起作用？
• 我被告知，为了找到参与者/投资者的子集，我们需要查看最小割集(S,T)，然后是：picked_investors = S ∩ investors和picked_actors = S ∩ actors。你能解释一下吗？
• 我们就不能看看这两个子集的流向吗？

Answer 1

该算法基于最大流-最小切割对偶性.让我们分析一下这张图中的最小部分是什么样子的。

我们可以很容易地看到有限的解决方案是可能的:考虑一边有{s}，另一边有其他节点的裁剪。显然，这个切割的值是q_i的和，它是有限的。

现在让我们来看看这张图中一个切线的含义。如果一个投资者在削减中与s站在同一一边，那就意味着他/她会投资他/她的钱。如果一个演员在剪辑中和s站在同一一边，那就意味着他也会参加这部电影。在剪辑的另一边意味着不参加电影(对演员和投资者来说)。

关键部分如下:任何不符合声明中规定的限制的削减都将具有无限的价值，因为从一个投资者到一个跨越这一限制的行为者都会有一个优势。正如我们以前所看到的，有限的解存在，因此一个极小的解将满足这些限制。

现在，我们要尽量减少什么？忽略无穷边，当我们为电影挑选那个演员时，就会增加一个演员的边缘，如果我们不为电影挑选那个投资者，就会增加一个投资者的边缘。我们想要最大限度地获得利益，这和尽量减少我们可能损失的东西是一样的。