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:关于最小生成树的最长边为所求的证明 Posted by:1120121860 at 2013-08-07 10:54:00 关键的地方在于第一步: “最小生成树T的最长边(u,v)小于等于任一生成树T的最长边” 更关键的在于等于的情况,也就是说可能存在另外一个生成树, 它不是最小生成树, 但它最长边等于最小生成树的最长边。 最小生成树一定是本题的解,但本题的解不一定只包括最小生成树。 这样本题就可能存在比最小生成树更快的解法 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator