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

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

Posted by Assassin_cpy at 2008-12-26 12:38:27 on Problem 2631
In Reply To:在某个论坛看到有人提供的一个待验证的算法，刚试了一下，是正确的，方法如下 Posted by:czcomt at 2008-12-25 18:34:14 
设最长链是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