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:倒是很轻松的AC掉了,但是怎么严格证明这个图一定是二分图? Posted by:Singularity25 at 2013-10-24 11:03:01 把每个点(x,y)转化成映射为(x+y, x-y) 这样做之后可以将两个坐标的变换全部都映射成奇数,由于奇数个奇数的和一定是奇数,无法形成环。 所以原图所有的可行环一定包含偶数条边,即是二分图。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator