编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

qsort+kruskal+rank

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

方法：快排边＋kruskal＋并查集＋不完全的路径压缩

要注意题目并不保证所有村庄一定是连通的！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

我真傻，真的，我一开始居然连那个S的限制条件都忘了判断。。。光读了干吗呢。。。WA了N次真是活该。。。

边少点多的时候kruskal最好用 怎么说也是O(nlogn)级别

注意图不连通的情况,因为有的点根本没有边与之相连,所以此时是'Impossible'的

为此WA了N次...... T_T

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

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

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

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

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

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

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

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

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

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

我做得太烦琐了

提交了N+1次

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

错了不知道多少遍,才发现....范围少个0,害得我把程序都该成牛头马面了...

速度比较慢

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

标准行输出 Need 16332255.17 miles of cable

错误行输出 Need 16332255.17 miles of cable.

（还有8组这样的情况，对了一个Impossible...）

狂晕中……

考前恶补并查集中。。。。。

puppy就是好，极糙算法也这么快

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

靠，这么慢……

并查+路经压缩+Kruskal+Qsort

编译通过...

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

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

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

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

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

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

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

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

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

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

只需路径压缩，无须启发试合并

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

信心大增

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

Qsort + Kruskal + 并查集

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

为什么同样是Qsort + Kruskal + 并查集..大家的300多MS就出来了..我的居然磨了3000多MS....而且并查集也用了路径压缩和启发式合并了啊??

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

没脸见人。。太慢了。。

很基础的图论题.

数据比较大,但还不至于BT.朴素的Kruskal+Qsort+并查集可以AC.

甚至粗糙一点的算法也没问题,因为时限是3s.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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