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

• Re:终于过了,讲下算法. (238) alpc60 2007-10-08 20:53:53
• Re:终于过了,讲下算法. (17) alpc60 2007-10-08 20:55:05
• 嗯 我的贪心也wa了 (10) wpt 2007-10-08 21:03:36
• 找到了无所谓的边之后一定要删除吗？我觉得删不删都可以... (0) qiqilrq 2007-12-11 17:14:52
• Re:按LZ的方法做果然行！ (14) ecust_xuchen 2008-07-23 13:52:26
• Re:终于过了,讲下算法. (308) ip96cns 2011-02-06 22:31:05
• Re:终于过了,讲下算法. (138) zzsx65zdf 2011-10-21 00:07:32
• Re:终于过了,讲下算法. (35) zhenghan3 2011-11-05 08:33:47