Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:终于过了,讲下算法.In Reply To:终于过了,讲下算法. Posted by:alpc07 at 2007-10-08 20:48:41 好算法!!!!!受教!!!! 我补充一下,一个for循环可以搞定,意思跟队列差不多,不过好听点吧。 如果一个图G的最大匹配M不是唯一的,那么必然在M中存在一条边e,使得图G删去这条边e之后, 匹配数不变。所以可以用更简单更好理解的方式写这个算法 M是图G的一个最大匹配 for each edge e in M' 在G中删除边 e M'=删除边e后的图的最大匹配 if(|M|==|M'|) 这个匹配行不通.... 在G中还原边 e 这样就得到M中哪个匹配不是唯一的。。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator