我相信您可以通过在稍微修改的约束条件下找到图中的最小割来解决这个问题。其思想如下 - 由于割的成本等于横跨割的总容量,因此我们可以尝试通过向图中的每个节点添加一条从该节点到t的容量为1的额外边来修改图形。直观地说,这意味着与s处于同一部分的每个节点都会对割的总成本贡献一个额外的成本,因为从该节点到t的边将穿过该边。当然,由于额外的容量,这肯定会搞乱实际的最小割。为了解决这个问题,我们应用以下变换 - 首先,将边的容量乘以n,其中n是图中节点的数量。然后给每个边加上1。这里的直觉是,通过将边缘容量乘以n,我们使得最小割的成本(忽略每个节点到t的新边)将是割的原始成本的n倍。当我们然后添加从每个节点到t的额外的一容量边时,这些边可能对割的成本产生的最大贡献是n-1(如果除t之外的图中每个节点都在与s相同的一侧)。因此,旧最小切割的成本是C,新最小切割(S,V-S)的成本是nC + |S|,其中|S|是与s在同一侧的节点数。
更正式地说,构造如下。给定一个有向容量图G和一个(源,汇)对(s,t),通过执行以下操作构建图形G':
1. 对于图中的每条边(u,v),将其容量乘以n。
2. 对于图中的每个节点v,添加一个容量为1的新边(v,t)。
3. 计算图中的最小s-t割。
我认为,图G'中的最小s-t割对应于在图G中与切割边在同一侧节点数量最少的最小s-t割。证明如下。假设(S, V-S)是G'中的最小s-t割,我们首先需要证明(S, V-S)也是G中的最小s-t割。采用反证法;为了矛盾,假设存在一种s-t割(S', V-S'),其成本低于(S, V-S)的成本。令G中(S', V-S')的成本为C',(S, V-S)的成本为C。现在,让我们考虑这两个割在G'上的成本。根据约束条件,C'的成本将为nC'+|S'|(因为切割点S'侧的每个节点都对切割线贡献了一个容量),而C的成本将为nC+|S|。由于我们知道C'
nC+|S| ≥ n(C'+1)+|S|=nC'+n+|S|
现在,注意到0≤|S|<n且0≤|S'|<n,因为与s在同一侧的节点最多可以有n个。这意味着
nC+|S| ≥ nC'+n+|S|>nC'+|S'|+|S|>nC'+|S|
但这意味着在G'中,(S, V-S)的成本大于G'中(S', V-S')的成本,这与(S, V-S)是G'中的最小s-t割的事实相矛盾。这使我们得出结论:G'中的任何最小s-t割也是G中的最小s-t割。
现在,我们需要证明,在G'中的最小s-t割不仅是G中的最小s-t割,而且它对应于G中与s同侧节点数量最少的最小s-t割。同样,这个证明采用反证法;假设(S,V-S)是G'中的最小s-t割,但是在G中存在一些比S侧节点更少的最小s-t割。将这个更好的割称为(S',V-S')。由于(S,V-S)是G'中的最小s-t割,它也是G中的最小s-t割,因此(S',V-S')和(S,V-S)在G中的成本都是C。然后,G'中(S,V-S)和(S',V-S')的成本分别为nC + |S|和nC + |S'|。我们知道nC + |S'| < nC + |S|,因为我们选择(S',V-S')作为在G中与S侧节点数量最少的s-t最小割。但这意味着(S',V-S')的成本低于(S,V-S),这与(S,V-S)是G'中的最小s-t割的事实相矛盾。因此,我们的假设是错误的,(S,V-S)是G中与S同侧节点数量最少的最小s-t割。这完成了构造的正确性证明。希望这可以帮到您!