带源汇配对约束的多源多汇Max flow（最大流）求解咨询

这类带一一对应源汇配对约束的多源多汇最大流问题，有两种成熟的求解思路，优先推荐第一种改造图结构的方案，复杂度和常规最大流算法完全一致：

方案1：图结构改造法（兼容所有常规最大流算法） #

在常规添加超源、超汇的思路基础上，新增一层配对隔离节点即可实现约束，具体操作步骤：

• 首先为每一对配对的源点s_i、汇点t_i，分别生成专属的中间源节点s'_i和中间汇节点t'_i
• 按如下规则连边：
  • 全局超源S到所有中间源s'_i分别连边，容量设为无穷大（如果对应源点s_i有最大流出上限，直接将容量设为该上限值即可）
  • 每个中间源s'_i仅和其对应的配对源点s_i连边，容量设为无穷大
  • 每个配对汇点t_i仅和其对应的中间汇t'_i连边，容量设为无穷大
  • 所有中间汇t'_i分别连边到全局超汇T，容量设为无穷大（如果对应汇点t_i有最大流入上限，直接将容量设为该上限值即可）
  • 保留原图中所有非源、非汇节点之间的原有边，容量和方向不变
• 改造完成后直接运行任意常规最大流算法（如Dinic、ISAP），得到的最大流结果完全满足源汇配对约束。

核心逻辑：通过中间节点强制流量路径只能走对应配对的链路，从根源上阻断了源点流量流入非配对汇点的可能，不需要修改原有最大流算法的实现。

方案2：转化为多商品最大流问题 #

如果你的场景需要同时区分不同配对的流量路径，可以将每一组源汇配对视为一种独立的商品，转化为多商品最大流问题求解：

• 每一种商品的源为配对源点s_i，汇为配对汇点t_i，所有商品共享图中边的容量
• 求解所有商品的最大流量之和，就是全局满足约束的最大流

注意：普通有向图的多商品最大流属于NP难问题，仅在无向图、边容量无限等特殊场景下有多项式解法，仅在需要区分流量路径的场景下选择该方案。

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