二分图多重匹配
1. 二分图匹配、二分图多重匹配
- 简洁定义：
- 二分图匹配：边数最多的匹配；
- 二分图多重匹配：规定一个点要与L条边匹配。同时根据是否有边权，可划分为：
- 二分图最大多重匹配；
- 二分图最大权多重匹配（二分图多重最佳完美匹配）；
- 联系：当
L == 1时，二分图多重匹配退化为二分图匹配。
2. 二分图多重匹配算法
- 二分图最大多重匹配：
- 在原图上建立源点S和汇点T；
- S向每个X方点连一条容量为该X方点L值的边，每个Y方点向T连一条容量为该Y方点L值的边；
- 原来二分图中各边在新的网络中仍存在，容量为1（若该边可以使用多次则容量大于1）；
- 求网络的最大流，就是该二分图多重最大匹配的值。
- 二分图最大权多重匹配：
- 在原图上建立源点S和汇点T；
- S向每个X方点连一条容量为该X方点L值、费用为0的边，每个Y方点向T连一条容量为该Y方点L值、费用为0的边；
- 原来二分图中各边在新的网络中仍存在，容量为1（若该边可以使用多次则容量大于1），费用为该边的权值；
- 求网络的最大费用流，就是该二分图多重最优匹配的值。
3. 典型例题