> 终于过了这道变态题,过几天就要省赛了,真希望省赛能碰到二分图匹配的题.
> 这道题是比较经典的2分图匹配.有人说可以贪心做,我不解..自己写的贪心有漏洞,所以默认为贪心是不行的.
> 这道题要先计算出最大匹配数,并把最大匹配表记录下来,然后把匹配到的边记录在队列里,然后依次删除,重新计算匹配数,如果匹配数减少说明此边是必须也是唯一的.如果一样说明这边存不存在都行,要从原来记录的最大匹配表中减掉此边.最后要对原来的二分图恢复.
> 就以这样的方法,就能过此题.