适配Ford-Fulkerson算法的人员-门分配流网络模型修正问询

针对原模型中存在带下界的边（中间节点到门节点的边下界为2），需将其转化为标准无下界流网络，具体修改步骤如下：

1. 节点调整 #

保留原有的源点S、人员节点P₁_{Pₙ**、**门节点D₁}Dₖ（k=⌈n/5⌉）、中间节点M₁~Mₖ（每扇门对应一个中间节点），新增超级源点S'和超级汇点T'。

2. 边的改造与新增 #

原边保留与调整 #

• 源点S到每个人员节点P_j的边：容量保持为1（确保每名人员仅被分配一次）。
• 人员节点P_j到其可达的门节点Dᵢ的边：容量保持为1（人员仅能前往可达门）。
• 持钥人员节点P_j到其可达门对应的中间节点Mᵢ的边：容量保持为1（统计该门的持钥人员数量）。
• 门节点Dᵢ到原汇点T的边：容量保持为5（每扇门最多容纳5人）。

带下界边的转化（针对Mᵢ→Dᵢ的边，原下界2、容量5） #

• 将Mᵢ→Dᵢ的边容量改为 5-2=3（去除下界后，剩余可调节的流量空间）。
• 从超级源点S'到门节点Dᵢ添加一条容量为2的边：用于满足该门至少需要2名持钥人员的下界需求。
• 从中间节点Mᵢ到超级汇点T'添加一条容量为2的边：用于承接该门必须流出的2个持钥人员流量。

跨原源汇的补充边 #

添加一条从原汇点T到原源点S的边，容量设为n（总人数，确保足够大）：用于让流循环，满足所有节点的流量守恒约束。

3. 可行方案的判定 #

• 计算从超级源点S'到超级汇点T'的最大流。
• 若最大流等于 2*k（所有S'到Dᵢ的边容量总和，即所有门的下界需求总和），且原汇点T到原源点S的边流量等于n（所有人员都被分配），则存在满足约束的人员分配方案。
• 此时，人员节点P_j到门节点Dᵢ的边若有流量1，即表示该人员被分配到对应门；中间节点Mᵢ到Dᵢ的边流量加2（原下界），即为该门的持钥人员数量。

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