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:请教该算法的正确性(我好像可以证明,但一直WA),感激不尽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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator