第一次竟然交错程序了..

PRIM就行，编起来简单

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

KRUSKAL 就是强

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

数据够弱

用Prim一次ac 数据有点弱。。

我不会做！！！

555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555（最终泪流成河，有谁能帮帮我！！！）

555 j打成i WA了N次 555

最小生成树

这题太难了，谁能干掉它，程序越简单越好

我说...是RP问题还是咋地...

一模一样的程序非得交两遍才过..

还以为prim真不行呢``

数据弱．．．．

用邻接矩阵＋O(n^2)的Prim都能过．．．．

调了半天，不是快排写错，就是并查集写错……

无言了，提交了N次……

另外此题难度3？？比NOIP2006的题都难？？要是NOIP考这样的题我就HAPPY了啊~~

不错 KRUSKAL+并查集+QSORT 一次AC

方法：Kruskal

缺点：又要写快排，又要写并查集，麻烦。（其他内容30行，kruskal用16行）

心得：基础啊！！！！图论算法原版AC……

繁忙的都市 各省青少年信息学奥林匹克竞赛 (Provincial OI) 竞赛原题

编译通过...

├ 测试数据 01：答案正确... 9ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 9ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：18ms

Prim吧..

Qsort+Kruskal+并查集

我比较倾向Kruskal，对Prim不是很熟。

预处理用Qsort按权排序边，再来顺序加边。

第一问输出n-1，第二问输出加的第n-1条边的权值。

Qsort+Kruskal+并查集

p.s此题是题库里难度3图论算法中最简单的一个了。

分析题目后，不难建立出题目对应的模型：给出一个有边权的图，要求其中的一棵生成树，使得这棵生成树的最大边权最小。

显然图的最小生成树是满足这个性质，下面用反证法证明最小生成树最大边权最小：

反设图中存在一棵生成树T，T中的最大边权小于最小生成树Tmin的最大边权。令e是Tmin的最大边。e将Tmin分成两个连通分块X和Y。由于Tmin是最小生成树，那么对于任意边 ,都有e’的边权大于等于e的边权——结论1。而T是图的一棵生成树，那么T中一定存在一条边e’’ 属于 集合，而且e’’的边权一定小于e的边权。这与结论1矛盾，因此最小生成树最大边权最小的结论是成立的。

因此只要用Prim或Kruscarl算法求出图的最小生成树即可。

Prim....过了...!

Prim跟边有什么关系吖...你每次枚举边就行了..判断起点和终点是否扩展到..

落散牛说得太恐怖了..但是好像我的prim趋于kruskal..

Kruskal。终于AC……感慨基础的重要~~~要不然也不会WA这么多次……

Qsort+Kruskal

绝对的MST，不过上面的两位牛为啥不支持Prim呢，难道Prim不能AC？