Eli*_*ion 2 algorithm computer-science graph
\n\n\n让
\na_1, ..., a_n演员。每个演员都有成本c_1, ..., c_n。此外，我们还有投资者，b_1,..., b_m每个投资者都愿意投入q_j给我们的电影投钱。一个投资者会在我们的电影中投入资金，前提是他所有喜欢的演员都会出现在我们的电影中。\n 当然，我们可能有多个投资者。找到参与者/投资者的子集以使我们的利润最大化（即投资总和减去工资总和）
基本上，解决方案是将某个顶点s通过权重边连接到每个投资者q_i。接下来，我们将每个投资者与其偏爱的参与者联系起来infinity。最后，我们将每个参与者连接到某个带有权t重边的顶点c_i。
然后，我们寻找最大流量。
\n\n我的问题是：
\n\n(S,T)，然后我们有picked_investors = S \xe2\x88\xa9 investors：picked_actors = S \xe2\x88\xa9 actors。你能解释一下吗？小智 5
该算法基于最大流-最小割对偶性。让我们分析一下该图中的最小割是什么样子的。
{s}我们可以很容易地看出有限解是可能的：考虑一侧具有切割而另一侧具有其他节点。显然，此切割的值是 的总和q_i，它是有限的。
现在让我们看看该图中的切口的含义。如果投资者与s削减的一方处于同一侧，则意味着他/她将投资他/她的资金。s如果演员与剪辑中是同一方，则意味着他也会参加这部电影。处于剪辑的另一边意味着不参与电影（对于演员和投资者来说）。
关键部分如下：任何不满足声明中给出的限制的削减都将具有无限的价值，因为从投资者到跨越削减的参与者都会有优势。正如我们之前所看到的，存在有限解，因此最小割将满足限制。
现在，我们要最小化什么？忽略无穷边，如果我们为电影选择该演员，则将演员边缘添加到价值中；如果我们不为电影选择该投资者，则添加投资者边缘。我们想要最大化利益，这与最小化我们可能的损失是一样的。