没有判断连通!

├ 测试数据 10：运行时错误...| 错误号: 207 | 无效浮点运算

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

Unaccepted 有效得分：90 有效耗时：243ms

+了判断.!

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

做了30分钟,,

主要注意:不用EXTENDED..REAL就足够

不然第10个点会WA,

还有,第10个点WA了是因为没有判断连通

可以+一句

if t>m then begin writeln('Impossible'); halt ;end;

m表示边数!

算法很简单:普通的KRUSAL..

就是QSOER+并查集``

完毕!

PS:这题有难度3这么大吗..

1已经足够了..

---|Orz_教主_iek

记录号 Flag 得分 记录信息 环境 评测机 程序提交时间

R842168 Accepted 100 From gnaggnoyil－

　 P1045 FPC Archer UBW 2008-9-17 19:47:06

From Vivian Snow

Kerry 的电缆网络

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

{$n+}

program Project1;

const lam=1e-20;

type e=record

u,v:longint;

len:extended;

end;

var eg:array[1..100000]of e;

fa:array[1..100000]of longint;

n,m,i:longint;

s,ans:extended;

procedure swap(var a,b:e);

var temp:e;

begin temp:=a;a:=b;b:=temp;end;

procedure heapify(k,o:longint);

var l:longint;

begin

l:=k;

if k shl 1lam then

l:=k shl 1;

if k shl 1+1lam then

l:=k shl 1+1;

if lk then begin swap(eg[l],eg[k]);

heapify(l,o);end;

end;

procedure buildheap;

var i:longint;

begin

for i:=m div 2 downto 1 do

heapify(i,m);

end;

procedure heapsort;

var k:longint;

begin

buildheap;

for k:=m downto 2 do

begin swap(eg[1],eg[k]);heapify(1,k-1);end;

end;

function find(m:longint):longint;

begin

if m=fa[m]then exit(m);

find:=find(fa[m]);

fa[m]:=find;

end;

procedure union(m,n:longint);

begin

m:=find(m);n:=find(n);

fa[m]:=n;

end;

begin

fillchar(eg,sizeof(eg),0);

readln(s);readln(n);m:=0;i:=0;

while not eof do

begin

inc(m);read(eg[m].u,eg[m].v);

readln(eg[m].len);

end;

heapsort;

for i:=1 to n do fa[i]:=i;ans:=0;

for i:=1 to m do

if find(eg[i].u)find(eg[i].v)

then begin union(eg[i].u,eg[i].v);ans:=ans+eg[i].len;end;

if ans-s>lam then write('Impossible')

else begin

m:=0;for i:=1 to n do if fa[i]=i then inc(m);

if m>2 then write('Impossible')

else write('Need ',ans:0:2,' miles of cable');

end;

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

对评测机无语了。。小号只要50MS。。。。。

注意写kruskal的时候要for en:=1 to m（边的总数） do

而不是while count

克鲁斯卡尔 谁能讲讲为什么seekeof不对啊？？？

where is m?

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

少了一个halt，90分，多wa了一次，囧

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

很简单的Kruskal。

并查集用rank和路径压缩。

我真个SHAX。。。一开始把m打成n了。。。wa了一次...

这题UFS+kruskal

关键要处理好细节！

WA了4次才AC,还可以吧.这是本人第一次编那个什么克鹭鸶卡尔算法,第二次编并查集.第一次WA是因为SEEKEOF,第二次90分因为连通图,第三次忘记更新用了原来的程序数组只有100的,10分,第四次连同图判断出错了,0分,第五次AC.还好自己算法本身没错,都是些小细节,不过细节是要命的啊!!

编译通过...

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

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

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

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

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

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

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

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

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

├ 测试数据 10：答案错误...程序输出比正确答案长

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

Unaccepted 有效得分：90 有效耗时：918ms

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

vijos dolphin是哪台机？机子慢还是我程序慢啊？

我把一个read改为readln就对了!!!!!!!!!!!!!!!!!!!!!!!

编译通过...

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

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

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

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

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

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

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

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

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

├ 测试数据 10：运行时错误...| 错误号: 207 | 无效浮点运算

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

Unaccepted 有效得分：90 有效耗时：2153ms

"├ 测试数据 10：运行时错误...| 错误号: 207 | 无效浮点运算"

这什么鬼东西？

岂有此理！是可忍，孰不可忍！

f***|!

其他没什么好提醒了，都说得很详细，但是如果你象我一样只有最后一个点过了，其他点都106错误的话，检查一下是不是用seekeof了，改成eof就可以了……

哈哈，终于AC了

最后一个点好可恶，害我交了N+1次

连通图的问题啊~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

竟然这么轻松的题目，做kruscal都不用union

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

为什么这么慢？。。

交了n遍

结果发现n和m搞混了。。。

竟然还对5个点~让我以为是精度的问题。。。。

晕。。。。。。。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

不加路径压缩似乎还快一点,不过都差不多