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:直接按题目给的边建图，求一次最大匹配，从而得到最小独立集。判断Yes,No,去掉匹配上任意的一边，再做一次匹配，如果去掉任意一边都可以达到原来最大匹配的值Yes,否则No

Posted by shixinfei at 2010-08-26 09:58:41 on Problem 3342
In Reply To:直接按题目给的边建图，求一次最大匹配，从而得到最小独立集。判断Yes,No,去掉匹配上任意的一边，再做一次匹配，如果去掉任意一边都可以达到原来最大匹配的值Yes,否则No Posted by:bluewind at 2007-08-14 21:57:32 
应该是去掉匹配的任意一边都达不到原来的匹配值才输出yes的吧，意思就是匹配是唯一的。
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