基于Ford-Fulkerson的儿童家务分配：如何实现任务数上下限约束？

要把「每名儿童至少3项、至多5项家务」的约束融入二分图，同时满足「同一儿童一天不能做两项」的要求，需要用带下界的流网络结合节点拆分的方法，具体步骤如下：

1. 节点拆分与定义 #

先通过节点拆分解决单日任务限制，再扩展流网络处理上下限约束：

• 超级源点 S'、超级汇点 T'：用于处理带下界的流需求
• 原始源点 S、原始汇点 T：对应常规流网络的源汇
• 儿童入节点：u1_in~u5_in：承接总任务数的上下限约束
• 儿童日期节点：u1_out_1~u1_out_10 到 u5_out_1~u5_out_10：每个儿童对应10天的输出端，限制每天最多完成1项
• 家务节点：v_1_1, v_1_2 到 v_10_1, v_10_2：共20个，每个对应某天的某一项家务任务

2. 边的配置（对应所有约束） #

（1）总任务数的上下限约束（3≤儿童任务数≤5） #

• 原始源点 S 到每个 u_i_in 的边：设置下界3，上界5
  • 转换为带下界流的标准形式：将这条边的容量改为 5-3=2（表示在满足最低3项后，最多还能分配2项），同时标记节点供需：S 的需求减3，u_i_in 的需求加3

（2）单日任务限制（同一儿童一天最多1项） #

• 每个 u_i_in 到对应的 u_i_out_d（d=1到10）的边：容量设为1，保证每天最多有1单位流流向当天的家务节点，即最多做1项

（3）偏好与任务唯一性约束 #

• 若儿童i偏好第d天的第k项家务 v_d_k，则从 u_i_out_d 到 v_d_k 连一条容量为1的边：仅允许有偏好的儿童分配该任务
• 每个家务节点 v_d_k 到原始汇点 T 的边：容量设为1，保证每项任务仅被1名儿童完成

（4）带下界流的超级节点连接 #

• 从超级源点 S' 到每个 u_i_in 连一条容量为3的边：强制给每个儿童分配至少3项任务的流需求
• 从原始源点 S 到超级汇点 T' 连一条容量为15的边：对应5个儿童×3项的总下限需求
• 从原始汇点 T 到原始源点 S 连一条容量为20的边（总家务数，足够大即可）：让流可以循环，实现带下界流的可行流求解

3. 求解与方案提取 #

• 计算 S' 到 T' 的最大流，如果所有 S'→u_i_in 的边都达到满流（流量3），且 S→T' 的边流量达到15，说明存在满足所有约束的分配方案
• 提取方案：若 u_i_out_d→v_d_k 的边流量为1，就表示儿童i在第d天完成第k项家务；统计每个儿童的总任务数，会自动满足3-5项的要求

如果最大流不满足满流条件，说明不存在符合所有约束的分配方案，可能需要调整儿童的偏好列表或约束条件。

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