基于最大流/最小割的双处理器总时间最小化求解困惑

你的流图建模核心误解 #

1. 边容量的赋值逻辑颠倒
   你将源点p1到模块节点vi的边容量设为Ai，vi到汇点p2的边容量设为Bi，这会导致割的权重与原问题总时间的对应关系完全错位。原问题中，模块i分配到A时需支付Ai，分配到B时需支付Bi，但你的赋值无法让割的权重直接映射到该成本项。

2. 通信边的建模错误
   你直接在vi和vj之间添加容量为cij的边，但未正确关联跨处理器通信成本的触发逻辑：只有当i和j分属不同处理器时，才需要支付cij。这种直接加边的方式无法让割的权重自动统计该类成本，反而会引入冗余计算。

3. 割与分配方案的映射关系未明确
   你未建立割的划分（S集合、T集合）与处理器分配的对应规则，也未推导割的权重如何等价于原问题的总时间，导致无法将最小割与最优分配方案关联起来。

正确的流图归约方案 #

流图构建 #

• 节点集合：源点s（对应处理器A）、汇点t（对应处理器B），每个程序模块对应一个节点v1, v2, ..., vn。
• 边集与容量：
  • 对每个模块i，添加边s → vi，容量为Bi；添加边vi → t，容量为Ai。
  • 对每对模块i,j（i≠j），添加双向有向边vi → vj和vj → vi，每条边容量为cij。

割与分配方案的对应 #

将割的划分(S,T)定义为：s ∈ S，t ∈ T；若vi ∈ S，则模块i分配到处理器A；若vi ∈ T，则模块i分配到处理器B。

此时，割(S,T)的权重等于该分配方案的总时间：

• 分配到A的模块vi ∈ S：需支付Ai，对应割中vi → t（从S到T）的容量之和。
• 分配到B的模块vi ∈ T：需支付Bi，对应割中s → vi（从S到T）的容量之和。
• 跨处理器的模块对vi ∈ S, vj ∈ T：需支付cij，对应割中vi → vj（从S到T）的容量之和；同理vj ∈ S, vi ∈ T时，vj → vi的容量cij也会被计入割的权重。

正确性证明 #

1. 任意分配方案对应割的权重等于总时间
   对任意分配方案，按规则划分S和T后，割的权重恰好等于分配到A的模块Ai之和、分配到B的模块Bi之和、跨模块通信成本cij之和的总和，与原问题总时间定义完全一致。

2. 任意割对应分配方案的总时间等于割的权重
   任意s-t割(S,T)对应的分配方案，其总时间的三个组成部分正好对应割权重的三个来源，二者数值相等。

因此，最小割的权重对应原问题的最小总时间，问题成功归约为最小割问题，可通过最大流算法（最大流-最小割定理）求解。

内容的提问来源于stack exchange，提问作者Jaka C