带专属边的二分图最大匹配问题求解咨询

你的问题核心是二分图带互斥容量约束的匹配，不是普通的二分匹配问题，直接修改Ford-Fulkerson的增广路逻辑行不通——原有算法只处理单节点的匹配调整，没法表达右侧节点“要么装3个普通节点，要么装1个专属节点”的互斥规则，更没法处理批量腾位的全局约束冲突。

正确的网络流建模方式 #

你需要重新构建网络流模型，通过节点拆分表达右侧节点的互斥容量规则，然后用标准的最大流算法（Ford-Fulkerson或更高效的Dinic）求解，不需要修改算法本身。具体步骤：

1. 定义源点S和汇点T。
2. 左侧节点处理：
   • 每个普通左侧节点N_i，从S到N_i连一条容量为1的边（每个普通节点只能被匹配一次）。
   • 每个专属左侧节点E_j，从S到E_j连一条容量为1的边（每个专属节点只能被匹配一次）。
3. 右侧节点处理（核心：拆分节点表达互斥模式）：
   对每个右侧节点R，拆分为3个节点：
   • R_choice：模式选择节点，从S到R_choice连一条容量为1的边（表示R只能选一种工作模式）。
   • R_normal：普通模式节点，从R_choice到R_normal连一条容量为1的边；从R_normal到T连一条容量为3的边（普通模式下最多容纳3个普通节点）。
   • R_excl：专属模式节点，从R_choice到R_excl连一条容量为1的边；从R_excl到T连一条容量为1的边（专属模式下最多容纳1个专属节点）。
4. 匹配边处理：
   • 所有能匹配右侧节点R的普通左侧节点N_i，向R_normal连一条容量为1的边。
   • 所有能匹配右侧节点R的专属左侧节点E_j，向R_excl连一条容量为1的边。

为什么这个模型能解决你的问题 #

以你给出的例子（左侧0、1为普通，2*为专属；右侧A、B）为例：

• 初始状态下，0、1匹配到A的普通模式，对应流路径是S→0→A_normal→T、S→1→A_normal→T，同时S→A_choice→A_normal有流1（表示A处于普通模式）。
• 当尝试给2*找匹配时，若想匹配到A的专属模式，算法会尝试构建增广路：需要把A_choice的流从A_normal切换到A_excl，这就要求0、1必须找到其他普通模式的节点（比如B的B_normal）。
• 若只有0能适配B，1找不到其他节点，这条增广路无法形成，算法会自动放弃将2匹配到A，转而尝试将2匹配到B的专属模式，不会出现你遇到的“强制腾位导致失效”的情况。

算法选择建议 #

不需要更换算法，标准的最大流算法（Dinic算法效率更高，适合节点数较多的场景）完全能处理这个模型。你之前的思路错误在于试图在二分匹配的框架下打补丁，而没有针对问题的约束重新建模。

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