Kruskal+Qsort+并查集（路径压缩）=O(NLogN)=AC

注意最后一个点

为了这

我多提交了10多次~~~~`

我用QSORT+KRUSKAL+并查集 过了9个点最后个点是剪枝才过的,可能是我的程序太烂以至于超时的吧.

剪枝为 1 :当发现当前的花费已经不能出解时就可以输出Impossible 了

2:还有可能不存在最小生成树,计算已经生成的点和最没求的点若加起来都不能够成生成树时也可以无解了

就这条,因为有大牛曾经说过极限数据很可能是无解的.

信不信随你便

惭愧啊,我的程序很慢的,没加RANK

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

哈哈 没用启发式合并都这么快

我的方法：先Qsort 然后用带并查集优化的Kruskal

最后再用并查集判断图是否包含全部点

我的并查集里没有加rank启发式合并 只加了路径压缩

结果如下：

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

我一直在纳闷为什么会TLE！！！

结果后来才知道，是因为我用了IOSTREAM！！！！！！

改了CSTDIO以后就AC了。。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

相信这是更加满意的速度

此题第10个数据异常诡异，竟然有一些点没有边

qsort+kruskal+并查集

AC

开始没注意，在cable后面加了一个“.”结果20分

改后100分

详见记录R64963

Kruskal……无奈中……

...要是早点看题解，就好了。。。。eof!............

这个是什么原因引起的。。

强烈要求

Hint: 使用eof，而不使用seekeof

我用 seekeof 读入只对了一个点，改成 eof 就AC了！

呃。。eof..seekeof..用seekeof竟然出问题了，残忍的对待我

我也是，并查集，强啊

还不错，路径压缩管用啊！

靠,第一次编KRUSKAL+QSORT+并查集(及路径压缩),WA了5.6次才过,共870MS,应该是一个不错的时间度,恩,满意中!!!

显然是求最小生成树,考虑到边数,用Kruskal方法来做.把所有边按长度排序后按从小到大加到树里,在判断有无环生成是用并查集来提高效率.排序可以用快排,但用堆的效果会更好!

点击查看程序源码+详细题解

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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