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

不产生环 那样例怎么出来的。。。。请提示一下~

Posted by Zeor at 2009-09-10 17:06:29 on Problem 1861 and last updated at 2009-09-10 17:06:42
In Reply To:未AC的请进 Posted by:OIer_cjf at 2009-01-22 14:34:47
> 题目大意:
> 给出顶点数,边数,再输入若干条边,求出若干条边满足条件:
> 1)这几条边中长度最大的长度尽量小;
> 2)这若干条边可保证图的连通性;
> 3)在1,2的基础上,求个MST
> 大致步骤:
> 1)边按长度排序.
> 2)把边按长度由小到大依次加进去(要求加入边后不产生环(并查集实现)).
> 3)输出这个最小生成树的信息.
> ______________________
> 从此题可以发现,Prim和Kruscal同样求最小生成树,但是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