Detail of message

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

说说一个简单的思路

Posted by Jungle_Crosser at 2010-08-22 17:07:12 on Problem 2253

我们首先将所给出的边的距离全部求出（共n*（n-1）/2 条），按距离总小到大排序。
最后选择的最优路径一定是从这里的边中挑选出来的。
将每个点看成一个集合。每加入一条边就将这两条边的端点所在的集合合并。
直到1点和2点并入了一个集合时停止。由于边是从小到大排列的，那么最后加入的一条边
就是达到目的的最短距离。

Followed by:

Re:说说一个简单的思路 (215) WonderStar 2010-08-23 21:46:12
Re:说说一个简单的思路 (181) Gsrq 2010-09-14 20:25:07
这不是Kruscal么.......... (0) slon 2011-03-05 22:15:11
Re:谢谢分享，算法的实质是贪心+并查集 (29) Once_HNU 2011-04-20 10:44:17

Post your reply here:

Home Page Go Back To top