> 题目大意:
> 给出顶点数,边数,再输入若干条边,求出若干条边满足条件:
> 1)这几条边中长度最大的长度尽量小;
> 2)这若干条边可保证图的连通性;
> 3)在1,2的基础上,求个MST
> 大致步骤:
> 1)边按长度排序.
> 2)把边按长度由小到大依次加进去(要求加入边后不产生环(并查集实现)).
> 3)输出这个最小生成树的信息.
> ______________________
> 从此题可以发现,Prim和Kruscal同样求最小生成树,但是Kruscal求出的生成树满足一个特性:这个生成树的最长边是尽量短的.

用prim生成的最长边也是尽量短的吧..

• Re:未AC的请进 (28) zhengchl 2009-04-12 19:48:30
  • Re:未AC的请进 (4) zhengchl 2009-04-12 19:48:57