| ||||||||||
| 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