Posted on 2011-03-26 21:53
Mato_No1 阅读(3160)
评论(2) 编辑 收藏 引用 所属分类:
网络流
在二分图最大匹配中，每个点（不管是X方点还是Y方点）最多只能和一条匹配边相关联，然而，我们经常遇到这种问题，即二分图匹配中一个点可以和多条匹配边相关联，但有上限，或者说，Li表示点i最多可以和多少条匹配边相关联。
二分图多重匹配分为二分图多重最大匹配与二分图多重最优匹配两种，分别可以用最大流与最大费用最大流解决。
（1）二分图多重最大匹配：
在原图上建立源点S和汇点T，S向每个X方点连一条容量为该X方点L值的边，每个Y方点向T连一条容量为该Y方点L值的边，原来二分图中各边在新的网络中仍存在，容量为1（若该边可以使用多次则容量大于1），求该网络的最大流，就是该二分图多重最大匹配的值。
（2）二分图多重最优匹配：
在原图上建立源点S和汇点T，S向每个X方点连一条容量为该X方点L值、费用为0的边，每个Y方点向T连一条容量为该Y方点L值、费用为0的边，原来二分图中各边在新的网络中仍存在，容量为1（若该边可以使用多次则容量大于1），费用为该边的权值。求该网络的最大费用最大流，就是该二分图多重最优匹配的值。
例题：
【1】POJ1698 Alice's Chance
将电影作为X方点，每一天作为Y方点（最多50周，每周7天，所以共设350个Y方点），若第i个电影可以在第j天搞就连边(i, j)。每个X方点的L值为该电影总共要搞多少天，每个Y方点的L值为1（每天最多只能搞一个电影），然后求二分图多重最大匹配，若能使所有从源点连向X方点的边都满流，则输出Yes，否则输出No。
【2】POJ2112 Optimal Milking
先预处理求出每两个点（包括挤奶点和牛）间的最短距离，然后将所有挤奶点作为X方点（L值为该挤奶点最多可以容纳多少牛），所有牛作为Y方点（L值为1），X
i和Y
j间边的权值为这两个点之间的最短距离（若这两点间不存在路径则此处无边），然后问题就变成了求一个多重匹配，使得每个Y方点都有匹配点且匹配边中权值的最大值最小。
可以枚举最大边权值S，然后，原图中所有权值大于S的边都要删去。若此时图中存在符合要求的多重匹配，则S合法否则S不合法。由于S的合法性是单调的，所以可以二分枚举S。