algorithm - 最大流量找到最赚钱的安排

Question

Let a_1, ..., a_n actors. Each actor has a cost c_1, ..., c_n. Also, we have investors, b_1,..., b_m such that each investor is willing to put q_j money for our film. An investor would put money in our film iff all of his favor actors, will be in our movie. We may have multiple investors of course. Find the subsets of actors/investors to maximize our profit (i.e. sum of investments minus sum of salaries)

基本上，解决方案是将一些顶点 s 连接到具有权重 q_i 边的每个投资者。接下来，我们将每个投资者与权重为 infinity 的参与者联系起来。最后，我们将每个参与者连接到某个顶点 t，边的权重为 c_i。

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

我的问题是:

• 为什么有效？
• 有人告诉我，为了找到参与者/投资者的那些子集，我们需要查看最小割(S,T)，然后我们有:picked_investors = S ∩ 投资者 和 picked_actors = S ∩ actors。你能解释一下吗？
• 我们不能只查看流去哪里来找到这两个子集吗？

Answer 1

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

我们可以很容易地看出有限解是可能的:考虑在一侧有 {s} 而在另一侧有其他节点的切割。显然，这个切割的值是 q_i 的总和，它是有限的。

现在让我们看看这个图中切割的意义。如果投资者在切割中与 s 处于同一侧，则意味着他/她将投资他/她的钱。如果 Actor 在剪辑中与 s 处于同一侧，则意味着他也将参与电影。处于剪辑的另一边意味着不参与电影(对于 Actor 和投资者而言)。

关键部分如下:任何不满足声明中给出的限制的切割都将具有无穷大的值(value)，因为从投资者到参与者都会有一个边缘穿过切割。正如我们之前所见，存在有限解，因此最小割将满足限制。

现在，我们要最小化什么？忽略无限边，如果我们为电影选择那个 Actor ， Actor 边就会被添加到值(value)中，如果我们没有为电影选择那个投资者，就会添加投资者边。我们想要最大化利益，这与最小化我们可能失去的东西是一样的。