Prim

...

秒杀囧

为什么放到DP题类里来

囧

样例有问题啊啊。。

跟楼下的楼下一样。。

样例没过照样秒。。

正在思考DP的我，无意中发现各位大牛用Prim给秒了..我也就打了个Prim...

另外，为什么数组开到1000会超时？而开到5000就能A？ N不是小于800么

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

寒...样例没过的程序竟然秒杀...

译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var

n,i,j:longint;

x,y:array[1..800]of extended;

a:array[1..800,1..800]of extended;

c:array[0..801]of extended;

e:array[0..801]of boolean;

m:extended;

begin

readln(n);

for i:=1to n do

readln(x[i],y[i]);

for i:=1to n do

for j:=1to n do

a:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));

for i:=0 to n do

c[i]:=131452013145201314520;

fillchar(e,sizeof(e),1);

e[1]:=false;

i:=1;

m:=0;

while true do

begin

for j:=1to n do

if(c[j]>a)and(e[j])

then c[j]:=a;

i:=0;

for j:=1to n do

if (c[j]

样例没过，却**Accepted**了

编译通过...

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

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

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

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

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

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

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

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

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

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

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

Unaccepted 有效得分：30 有效耗时：0ms

好恐怖!

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

PRIM!

听说周长减最大边也能过,但是样例不能过,难道数据真的很弱?

MST是正解..

同意楼下 这题不好

这种题也不删？？？？

program aa;

var x,y,l:array[0..800] of real;

map:array[1..800,1..800] of real;

vis:array[1..800] of boolean;

i,j,n,k,a,b:longint;

r,e,s,min:real;

Begin

readln(n);

for i:=1 to n do

readln(x[i],y[i]);

for i:=1 to n-1 do

for j:=i+1 to n do

begin

map:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));

map[j,i]:=map;

end;

fillchar(l,sizeof(l),$7f);

s:=0;l[1]:=0;

for i:=1 to n do

begin

k:=0;

for j:=1 to n do

if (not vis[j])and(l[j]

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

晕，，我用KRUSAL，，

数组要开到1000000···哈哈

郁闷死了，，

开小了只有20分！！

水题？烂题？错题？让人读不懂的题！！！

题目叙述不清，样例错误？

dp？我用周长-最长边，秒杀……

数据太烂！

ps：那位大牛会这题的dp告诉我

为什么我的prim总是过不了最后两个点呢？

写了个prim就过了...

这个是黑书上的题目（黑书上这题叫做青蛙的烦恼）..到了这里数据太弱，结果....

诶

这也太无敌了

样例用prim能得到、并AC

用周长减最长边AC，但得不到样例

{太搞了吧}

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

周长减最长边就过了，………………

这叫什么动态规划

很冷的笑话

周长减最大边哈哈哈哈哈哈我快笑翻了