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

Re:说说一个简单的思路

Posted by Gsrq at 2010-09-14 20:25:07 on Problem 2253
In Reply To:说说一个简单的思路 Posted by:Jungle_Crosser at 2010-08-22 17:07:12
> 我们首先将所给出的边的距离全部求出(共n*(n-1)/2 条),按距离总小到大排序。
> 最后选择的最优路径一定是从这里的边中挑选出来的。
> 将每个点看成一个集合。每加入一条边就将这两条边的端点所在的集合合并。
> 直到1点和2点并入了一个集合时停止。由于边是从小到大排列的,那么最后加入的一条边
> 就是达到目的的最短距离。

Kruscal

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