Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:终于过了,讲下算法.

Posted by ip96cns at 2011-02-06 22:31:05 on Problem 1486 and last updated at 2011-02-07 00:01:37
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator