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:对prim算法算出的结果表示怀疑,以上回答都不能充分证明这个问题。。

Posted by ZxyElf at 2013-03-10 14:15:41 on Problem 2485
In Reply To:对prim算法算出的结果表示怀疑,以上回答都不能充分证明这个问题。。 Posted by:swust20105592 at 2011-12-20 19:06:49
最小生成树的边权序列是唯一的。网上很多证明。
如果有另一个路网满足要求,且最大边权L比最小生成树中T的最大边权l小。
那么路网连通,有最小生成树t.
(1)如果L的边不在最小生成树t边,显然矛盾.
(2)L的边在t中.那么对于T的最大边(u,v).t中有一条u->v的路径.且路径上边权均不大于l.用其中一边替代(u,v).即(u,v)是原图中某个回路的唯一最大边.故不存在包括(u,v)的原图的最小生成树。与T是原图的最小生成树矛盾.

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