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:Jungle_Crosser at 2010-08-22 17:07:12 > 我们首先将所给出的边的距离全部求出(共n*(n-1)/2 条),按距离总小到大排序。 > 最后选择的最优路径一定是从这里的边中挑选出来的。 > 将每个点看成一个集合。每加入一条边就将这两条边的端点所在的集合合并。 > 直到1点和2点并入了一个集合时停止。由于边是从小到大排列的,那么最后加入的一条边 > 就是达到目的的最短距离。 Kruscal Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator