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 Ruby931031 at 2012-09-07 23:39:31 on Problem 2349 
很多人用的算法都是Prim求最小生成树，然后将MST中的边排序，第S长的边就是结果。
貌似有些道理但又不够严谨。下面这个证明很好（其中第12页）：
http://wenku.baidu.com/view/e4cd9e6648d7c1c708a145ac.html
我用上面的算法16ms过掉的……
不过，要想到这个算法确实很难啊……

过几天再用最小K度限制生成树做一下这题练练手吧，看看要用多久。
（虽然目测肯定会慢很多，写起来也很复杂，不过用最小K度限制生成树建模却是最自然的）
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