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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

Re:可证.昨晚证过了.内详.

Posted by luoax084 at 2009-05-11 22:54:41 on Problem 2631
In Reply To:可证.昨晚证过了.内详. Posted by:Assassin_cpy at 2008-12-26 12:38:27
> 设最长链是MN->已知[1]
> 设由B开始DFS得到最长路为BC->已知[2]
> 结论[1] MN与AB有公共点.否则MN<AM+AN<=AM+AB=BM 与已知[1]矛盾
> 结论[2] B是最长链的一个端点.否则由结论[1] 设K是AB上距B最近且在MN上的点 则MN=MK+KN=MK+AN-AK<=MK+AB-AK=MK+BK=BM 当取等号时MB与MN等长 符合结论[2] 否则与已知[1]矛盾  [这里假定了A不在NK上.若A在NK上 只须将上面式子中MN交换位置即可 不影响结论]
> 结论[3] BC是一条最长链.否则由结论[2] 设经过B的最长链为BD 则BD>BC 与已知[2]矛盾
> 至此证毕

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