二分图多重匹配.doc

《二分图多重匹配.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二分图多重匹配问题多重匹配是建立在单重匹配的基础上的，我们先回顾下单重匹配的时候，我们用一个数组cm[i]来表示与i匹配的点，而多重匹配的时候我们用的是一个结构体：structp{intgirl[MAXN],num;}cm[MAXN];其中cm[i].num代表当前已经有多少个与i进行匹配了，与之匹配的点保存在cm[i].girl[]中。还有一个不同的地方是在找增广路的时候，单重匹配是直接判断cm[i]是否等于-1，即是否已经匹配过，如果没匹配过则找增广路结束，否则沿着cm[i]继续找增广路。多重匹配也是相似的方法，如果与cm[i]匹配的个数少于最大可匹配数的时候，同样找增广路结束，否

2、则沿着所以与cm[i]匹配的点继续找增广路，只要其中有一个点找到了增广路就可以了。关键代码如下：if(cm[i].num

3、量为cj，如果GGj想要包养MMi，则连一个iàj，容量为INF的边。然后从S到T求一次最大流，最大流值就是所求的答案(证明略)。