把候选安排逐个加入日程时，先选中的一对可能妨碍后续分配。若每位人员最多接受一项任务，每项任务也最多分配一人，这个问题可以表示成二分图匹配。提高匹配大小有时需要撤销一对已有安排，换成两对新安排；26篇残量网络中的撤销操作正好表达这种调整。

本篇先证明匹配与整数流的对应，再从终止时的残量可达集合构造最小点覆盖。匹配是可行安排，点覆盖则限制任何安排最多能有多少对，两者大小相等时形成可核对的最优性证书。

两侧顶点不能混成一个编号域

输入左侧a个顶点、右侧b个顶点，以及m条候选边(l,r)。左侧编号0到a−1，右侧编号0到b−1，即使数字相同也表示不同对象。边保留输入ID，允许重复候选，但匹配不能重复使用任一端点。

输出一组匹配边ID，以及分别位于左右两侧的点覆盖集合。点覆盖要求每条输入边至少一个端点被选中；匹配则要求所选边两两不共享端点。这两个“覆盖”和“配对”条件不同，不能只比较返回集合的大小。

允许一侧为空、没有边、存在孤立点。不要求把所有人员或任务配满；目标是最大化匹配条数。加入边权、人员容量或任务优先级以后，需要重新说明目标和归约，不能直接沿用本篇最大基数匹配的结论。

单位容量强制每个对象只使用一次

构造源s、汇t及两侧顶点。每个左点连一条s→l，每条候选边连l→r，每个右点连r→t，容量全部为1。新图有N=a+b+2个顶点、M=m+a+b条边。

任意大小k的匹配都能生成值k的流：每条匹配边对应一条s→l→r→t的单位流路径。端点不重复保证源侧与汇侧容量不会被突破，内部顶点也满足守恒。

反过来，26篇实现从整数零流开始，始终给出整数流。对每个左点，入流至多1，因此它至多有一条候选出边流量为1；每个右点也至多接受一条。取全部流量为1的候选边，就得到匹配，其大小等于流值。

重复候选会形成平行边，但同一左、右端点的外侧单位容量仍然限制至多选一条。整数流是反向对应的必要部分：若只给出任意分数可行流，不能把每条正流候选都选成匹配。

这两个方向共同证明最优值相等。仅说明“匹配能变成流”只建立了一个方向的界，还不足以完成归约正确性证明。

增广路对应交替调整

未使用的候选边有左→右的正向残量；匹配边则有右→左的反向残量。从一个尚未匹配的左点出发，沿未匹配边、匹配边交替前进，若到达尚未匹配的右点，就得到增广路。

沿路交换“选中”和“未选中”，内部顶点仍恰好使用一次，两个原先未匹配的端点变成匹配，匹配条数增加1。若只允许新增边，不允许撤销匹配边，就会把极大匹配误当作最大匹配。

例如候选边为A→1、A→2、B→1。先选A→1后，没有单条边能直接加入，所以它是极大的；但B→1→A→2是一条交替增广路，交换后得到B→1和A→2，大小从1变成2。24篇的贪心交换证明不能仅凭“当前无法加入”就成立。

从残量可达集合恢复点覆盖

最大流结束后，26篇返回源点在正残量网络中的完整可达集。分别取其中的左点Z_L和右点Z_R，构造

C=(L∖ZL)∪ZR.C=(L\setminus Z_L)\cup Z_R.

源点直接到达所有未匹配左点；候选残量方向正好对应前述交替搜索。最大性保证无法到达未匹配右点，否则还能到达汇点并增广。

先检查C覆盖所有边。若某条未匹配边的左端不在C中，它就属于Z_L；正向残量使右端也属于Z_R，因而右端在C中。对一条匹配边，右端可达时能沿反向残量到达左端；左端可达时也必然由其匹配右端进入，因为该左点的源边已饱和。因此匹配边两端同时可达或同时不可达，恰有一个端点属于C。

未匹配左点都在Z_L中，不属于C；未匹配右点都不在Z_R中，也不属于C。因此C只从每条匹配边选出一个端点，大小等于匹配大小。

任意点覆盖都至少需要为匹配中每条边提供一个端点，而这些匹配边彼此不共享端点，所以任意覆盖大小不小于任意匹配大小。当前构造达到等号，同时证明匹配最大和点覆盖最小。这就是二分图上的König等式在本实现中的证书形式。

二分图条件不可删除

三角形最大匹配只有1条边，因为任意两边共享端点；最小点覆盖却需要2个顶点，一个顶点无法覆盖对面的边。它不是二分图，所以匹配大小等于最小点覆盖大小的结论不适用。

把同一个一般图顶点复制到左右两侧再连边，会产生另一个问题；两份副本可能分别被使用，不能据此声称解出了原图匹配。本篇输入明确给定两个不相交的顶点域，不负责把任意图自动转成等价的二分问题。

复用最大流后的成本

实现只负责构图和提取证书，增广仍调用26篇max_flow。每条增广路瓶颈为1，每轮匹配条数增加1，所以增广次数至多k=min(a,b)。连同构图与最后失败搜索，时间为O(N+(k+1)M)，空间O(N+M)。这个界属于当前单位容量归约与BFS实现，不是更专门匹配算法的最优复杂度声明。

提取匹配边、点覆盖和检查证书都可在线性时间内完成。采用整数算术单位成本模型，算法没有随机选择；这里的确定性最坏界也不等于Python任意规模整数的实际位操作成本。

可复跑检查

教学实现位于examples/advanced-algorithms/bipartite_matching.py。从仓库根目录运行：

1
python3 examples/advanced-algorithms/check_bipartite_matching.py

参照分别枚举候选边子集和顶点子集，独立求最大匹配与最小点覆盖。返回值另外接受边ID合法、匹配端点不重复、覆盖全部边和两者大小相等的检查。

本次实际运行通过689个左右侧均不超过3点的穷举图，对照21304个匹配子集和37477个覆盖子集；固定种子20260920的100个随机多重图，对照5511与6288个子集。另通过4个边界图和5个非法输入拒绝检查。输出保存于examples/advanced-algorithms/results/bipartite_matching.json。

这些有限检查没有代替归约两方向与点覆盖证明。子集枚举只用于小输入参照，不参与生产算法的成本界；本篇也没有实际运行时间或大规模排班性能数据。

练习

  1. 对A→1、A→2、B→1的例子，分别从大小1和大小2的匹配出发画出交替可达集合。为什么只有最大匹配终止时才能保证构造的点覆盖与匹配同样大？
  2. 给一个含孤立点、重复候选的二分图，手工给出匹配与同值点覆盖。检查器需要哪些条件，才能拒绝“条数正确但重复使用同一人员”的错误匹配？

参考资料