如何求解带放大边的最大整数流？附糖果分配问题建模示例

一、问题定义 #

1. 带放大边的最大整数流 #

这类流网络中，当流量流经放大值为w的边时，1单位输入流量会转化为w单位输出流量，目标是求解网络中的最大整数流。

2. 糖果分配优化问题 #

这是带放大边流问题的具体应用场景，核心需求如下：

• 输入：
  • n种普通糖果，每种存量为q[i]；
  • m个孩子，每个孩子对应：满意度矩阵s[j][i]（孩子j每获得1个i类糖果的满意度）、满意度阈值c[j]（满足孩子j的最低总满意度）；
  • 万能糖果：可为任意孩子贡献1单位满意度，数量无限制。
• 目标：
  • 分配普通糖果并按需使用万能糖果，满足所有孩子的满意度阈值；
  • 最小化万能糖果的使用总量。
• 约束：
  • 每种普通糖果的分配总量不超过初始存量q[i]；
  • 每个孩子可接收任意数量的各类糖果。
• 输出：二维数组形式的普通糖果分配方案，分配方案[j][i]代表给孩子j分配的i类糖果数量。
• 规模约束：n < 1e2，m < 1e3，q[i] < 1e4，s[j][i] < 1e2，c[j] < 1e5。

二、问题转化：糖果问题→带放大边的流网络 #

将糖果分配问题建模为带放大边的流网络，节点与边的定义如下：

节点设置 #

• 源点s：代表糖果的初始供应端；
• 糖果节点q₁, q₂, ..., qₙ：分别对应n种普通糖果；
• 孩子节点c₁, c₂, ..., cₘ：分别对应m个孩子；
• 汇点t：代表孩子的满意度需求端。

边的设置（格式：[起点, 终点, 容量, 放大值]） #

• 源点→糖果节点：[s, qᵢ, q[i], 1]，表示第i种糖果的总供应量为q[i]，流量无放大；
• 糖果节点→孩子节点：[qᵢ, cⱼ, ∞, s[j][i]]，表示第i种糖果可任意分配给孩子j，每1个糖果转化为s[j][i]单位满意度（即流量放大倍数为s[j][i]）；
• 孩子节点→汇点：[cⱼ, t, c[j], 1]，表示孩子j需要至少c[j]单位满意度，流量无放大。

模型对应关系 #

• 流网络的最大流量等于普通糖果能提供的总满意度；
• 万能糖果使用量 = 所有孩子满意度阈值总和 - 最大流量，这正是需要最小化的目标。

三、示例解析 #

输入示例 #

q = [5, 2, 1]
s = [
  [2, 3, 1],
  [1, 2, 3]
]
c = [15, 10]

对应流网络边列表 #

([start_node, end_node, capacity, amplification])
[
  [s, q1, 5, 1],
  [s, q2, 2, 1],
  [s, q3, 1, 1],
  [q1, c1, inf, 2],
  [q2, c1, inf, 3],
  [q3, c1, inf, 1],
  [q1, c2, inf, 1],
  [q2, c2, inf, 2],
  [q3, c2, inf, 3],
  [c1, t, 15, 1],
  [c2, t, 10, 1]
]

最优流结果 #

[
  [s, q1, 5],
  [s, q2, 2],
  [s, q3, 1],
  [q1, c1, 5],
  [q2, c1, 2],
  [q3, c2, 1],
  [c1, t, 15],
  [c2, t, 3],
]

• 最大流量为18，即普通糖果提供的总满意度为18；
• 万能糖果使用量 = (15+10) - 18 =7，符合最优要求。

对应的糖果分配方案 #

[
  [5, 2, 0],
  [0, 0, 1]
]

表示给第一个孩子分配5个1类糖果、2个2类糖果；给第二个孩子分配1个3类糖果。

四、带放大边的最大整数流求解思路 #

带放大边的流问题可通过转换为标准最大流问题求解，针对本问题规模，推荐采用Dinic算法变种：

1. 残量网络调整：对于放大倍数为w的边u→v，推送f单位流量时，u的流出量减少f，v的流入量增加f×w；
2. 反向边处理：推送f单位反向流量时，v的流出量减少f，u的流入量减少f×w；
3. 整数流保证：由于所有输入参数为整数，放大倍数为整数，调整后的算法可直接得到整数解。

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