最小点覆盖：每条边都有一个点被选
- 最小权点覆盖>=最大匹配数
- 证明等号成立。
- 构造方案：
- 从左边所有非匹配点出发，跑一遍增广，标记路径上的点
- 左边所有未被标记的点和右边所有标记的点组成一种方案
- 左边非匹配点一定被标记，右边非匹配点一定不被标记
- 对于匹配边，要么同时被标记，要么同时不被标记
- 左边非匹配点->右边匹配点，右边匹配点一定被标记，右边会被选择
- 左边匹配点->右边非匹配点，左边匹配点一定不被标记，左边点会被选择
Skip to content