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:请教该算法的正确性(我好像可以证明,但一直WA),感激不尽

Posted by lowever at 2012-03-19 14:55:55 on Problem 2942
In Reply To:Re:请教该算法的正确性(我好像可以证明,但一直WA),感激不尽 Posted by:Gamor at 2010-10-21 15:17:21
> 
> 
> 一个块若无法做二分图染色,势必存在一个长度为奇数的环
> 任找一个奇环C,则对于任意一个非环上的点A,一定有两条不相交的路,连向这个奇环,交奇环于两个不同的点P、Q(否则这就不是一个双连通分量)
> 
> 那么在环C上有两条P-->Q的路径,一条经过奇数条边,一条经过偶数条边
> 其中一条同PA、AQ相连后,一定是个奇环,所以A一定也在一个奇环上
>  膜拜AlNo3,这段话写得很好。 

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