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

• Re:未AC的请进 (15) iShowFun 2009-02-18 13:45:30
• Re:未AC的请进 (302) KosonLau 2009-03-20 01:08:59
  • Re:未AC的请进 (28) zhengchl 2009-04-12 19:48:30
    • Re:未AC的请进 (4) zhengchl 2009-04-12 19:48:57
• 不产生环 那样例怎么出来的。。。。请提示一下~ (280) Zeor 2009-09-10 17:06:29
  • 这个生成树的最长边是尽量短的？应该是尽量长的把// (0) 201151122 2013-04-07 21:00:09
• 但sample明显有环牙 (280) Pzjay 2009-10-25 19:18:47
  • Re:但sample明显有环牙 (109) 200730690105 2009-10-25 19:27:05
    • 顶一下... 我看见sample里的环也蒙了... (2) bobobo 2009-11-10 22:56:31
      • Re:顶一下... 我看见sample里的环也蒙了... (10) soul11201 2013-04-09 15:32:10
        • Re:顶一下... 我看见sample里的环也蒙了... (31) soul11201 2013-04-09 15:32:58
• Re:未AC的请进 (280) Psuanle 2010-11-19 00:06:15
  • Re:未AC的请进 (16) a86552271 2011-08-10 16:52:56
• 汗……sample完全请无视，考的就是就是Kruscal算法 (27) h2952220 2012-05-08 19:30:58