题解 - Vijos

0
huhao LV 7 @ 2019-08-11 09:39:00

%%% ljf czy fthl
0
oimaster LV 10 @ 2010-03-16 22:57:50

看了半天题解，终于AC了，原来不是Kruskal，是DP！

后来我用Prim+配对堆也AC了……优化了半天常数……
0
zck123 LV 7 @ 2008-10-31 23:26:50

kruskal+并查集过不了，数据太强大了
0
Fengyunfly LV 8 @ 2008-10-29 18:15:58

使用教主的KRUSKAL被卡住了。。

编译通过...

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

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

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

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

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

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

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

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

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

Unaccepted 有效得分：70 有效耗时：731ms
0
fengyi LV 9 @ 2008-10-28 21:01:11

我是大SB，每次都被师父的题虐死。
0
zlqiszlq LV 9 @ 2008-10-25 09:24:01

我便的KRUSKAL为什么不能ac？
0
orz教主_tangky LV 7 @ 2008-10-20 21:38:08

我只是不知道有没可以AC的Kruskal

毕竟nlogn和n的差距很小

而且我也没太卡常数

我60W卡的就是Kruskal
0
fjxmlhx LV 10 @ 2008-10-20 20:19:00

克鲁斯卡尔，每一个点只需存与他上方的点的边，和他对面的两个点（如果Y轴有相同的只需要存一个）
0
个性傲气 LV 8 @ 2008-10-20 17:37:45

编了个Kruskal，限时２Ｓ过了，交这里才２０．．．．
0
sanyun0606 LV 8 @ 2008-10-20 14:36:29

……数据也太大了吧……
0
qq646107182 LV 4 @ 2008-10-20 11:40:10

教主的标程好强大...
0
linshutan LV 3 @ 2008-10-19 16:53:57
- -||不行了.
  裸Kruskal..无法用..
教主我ORZ..
0
caotong0 LV 3 @ 2008-10-19 16:01:58

……………………dp
0
thomas0726 LV 4 @ 2008-10-17 14:17:05

终于有地板了
-1
guzhifeng LV 8 @ 2014-07-17 20:26:14

###克鲁斯卡尔+*qsort*能A吧
-1
z55250825 LV 10 @ 2013-11-01 10:30:20

终于用克鲁斯卡尔A掉了...虽然提交了N次....
关键在于多删边...如果有 (x1,y1)(x1,y2)(x2,y3)的话，若有(y1<y2<y3)，教主证了(x1,y1)(x2,y3)可以不连边，然后加了这个优化之后就真的A了....ORZ....
-1
voyagec2 LV 10 @ 2010-03-12 18:47:30

Orz 教主。。太硬了
-1
jacklv LV 10 @ 2009-11-06 20:05:54

编译通过...

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

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

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

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

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

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

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

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

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

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

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

Accepted 有效得分：100

有效耗时：684ms

orz教主的题都很不错啊，orz tky
-1
yzl609271536 LV 10 @ 2009-11-06 08:59:21

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

总算过了
-1
ufo172849z LV 10 @ 2009-08-17 00:21:17

可以用prim过掉，优化的思路就是根据教主的题解中的一些结论推广来的。

写的第一个程序算法没问题，但是暴空间了。所以只好把链表都删掉，重新写了一半的代码。

prim的复杂度可以降到O(nlogn)。而且常数是4。

最后的时间：

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

如果用extended不用double第9个点会207错误，