program vijos1045(input,output);

var

v:array[1..200000] of real;

sum:real;

a,b:array[1..200000] of longint;

p:array[1..200000] of longint;

x1,x2,m,i,j,k,l,n,w,e,q,x:longint;

s:real;

function find(x:longint):longint;

var

i,j,k:longint;

begin

if p[x]=x then exit(x)

else begin

p[x]:=find(p[x]);

exit(find(p[x]));

end;

end;

procedure qsort(head,tail:longint);

var

i,j,k,x,y:longint;

z:real;

begin

i:=head;

j:=tail;

x:=a[head];

y:=b[head];

z:=v[head];

while i

FUNCTION FIND(Q:LONGINT):LONGINT;

BEGIN

IF FA[Q]=0 THEN FIND:=Q ELSE BEGIN FA[Q]:=FIND(FA[Q]); FIND:=FA[Q]; END;

END;

这不是路径压缩么？怎么时间这么 快- -||...

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

时间好丑

SMDCN还是不行

ans

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

如何才能秒杀？

function top(i:longint):longint;

begin

if if[i] then f[i]:=top(f[i]);

top:=f[i];

end;

这个能不能算 并查集压缩？

编译通过...

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

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

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

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

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

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

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

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

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

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

水杀了，puppy=0ms

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

没秒杀，尴尬。

UFS+Quicksort+Kruskal+puppy=0ms

当然 Heap+Prim 也可过 个人感觉时间上不如Kruskal 人家怎么说也是O(E)呀……

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

写的真WS！

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

好丑的时间。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

并查集强大啊！！！

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

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

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

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

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

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

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

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

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

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

为什么差这么多..第10个数据竟然是无法生成树,我囧

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

好吧.......本小菜第一次写Kruscal.......

Sunny好慢......刚才Puppy测得90分9ms的说.....

切记判断无解情况.......囧死了

刚开始 n m 弄错了.........交了好多次......

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

晕,把并查集写错了!!!!!!!!郁闷!好快啊!

非常丑的Kruscal+普通并查集……

使用iostream的结果……

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

使用cstdio的结果……

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

再在并查集里面加入路径压缩……

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

路径压缩大好……

以及iostream我恨你……

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

时间基本还可以……我写的朴素的kruskal

HINT：一个提时间的优化当n-1>m时无解……1次AC

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

写丑了没秒杀真尴尬

kruskal+快排+并查集

MST-Kruskal,基本是裸的,就穿着一点点......

多亏了并查集

并查集是好东东

这道题通过率怎么这么低......

我也来纪念 个人提交200次

第1220个AC这道题

Flag 　　Accepted

题号 　　P1045

类型(?) 　　图结构

通过 　　1220人

提交 　　6881次

通过率 　　18%

难度 　　3

好几次因为5,6,7几个点输出的Impossible错的。

贴一个简陋的代码...

for (int i=1;i