图，经典算法

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

AC119题，冲到2.5星了，可是依然很菜

郁闷，虽然知道周长减最大边是错的，还是试了试……

第二个点 6.82……

7.92……

也许有人过了是加了这么条

if(result==7.92……)

result-=1.1

这也太卑鄙了吧

实际上是个 最短哈密顿路径

其实是个很好的题目，可能数据烂了点。。

虽然我没做……不过还是从黑色上抄点下来吧。

其实DP的关键是，这些点组成一个凸多边形。

据此，可以推出不能有相加的边，然后可以实现DP了

标准算法是DP，看黑书133到134页。

还有题目描述有问题，不一定从1号点开始……

对此题彻底无语。

先写了朴素DP。50分。

检查了半天找不到错，胡乱改了个地方，还是50分。

看题解，都是错误的生成树算法。忽略。

然后开始改程序，因为看到讨论里面说不一定是从第一个点开始走（我汗）。

改了之后交上去，无效浮点运算？！0分！

看了半个小时程序没有思路，想想把double改成extended，就AC了？！

太怪了。如果double无效浮点运算的话，为什么之前还能有50分啊？！

而且题目描述绝对有问题！不一定从第一个点开始。

为什么prim死活过不了，而kruscal一次AC？

在网上找了下题解，居然有解析说样例是错的。。。

实际上周长减最大边的方法用样例就可以否掉，样例的四个点构成一个平行四边形，选择两最短边和一对角线就可以得出样例结果。

正确的方法应该是求哈密顿链。。。

数据弱导致的后果......

一开始由于以为第一个点就是起点而WA了N次。。。。。。

虽然没有秒杀，但程序30行足以。

在此告戒周长减最大边的大牛，能AC纯属数据太弱，因为没有任何可以证明这个说法的证明，正解绝对是DP。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program vijos;

var i,j,k,n:integer;

d,g,f:array[1..800,1..800] of extended;

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

function min(x,y:extended):extended;

begin

if x

用周长减最长边的朋友，

如果第2个点WA了，

去看看该题提交记录，可能会有所启发！

不可能用周长减去最长边吧？

题目上说“编号为1的人就坐在大门口，xiaomengxian必须从这里出发去拿其它的红包。一条合法的路线必须经过所有的点一次且仅一次”！！

可是好像那样做能过9个点，真的搞不懂

好诡异啊！！

我用DP过了5个点；

用周长减去最长边又过了5个点；

然后合起来提交

AC！！！

无语了！！

掉RP！

怎么有可能是最小生成树呢？

没个点只可以经过一次。

应该是用DP求多个点围成的多边形的最小周长，

不过如果这样用贪心可以贪很多数据的....

贪心算法如下：

任意选出一个点，查找一个与它最近并没有标记的点，标记，递归.....

然后减去最长边就OK

太无聊了!!!

原来可以不用从第一个人出发

害我不知道调了好久!!!

严重bs题目描述!!!

我觉得最小生成树是错的，除非你会分身

尽管我也用的MST……

编译通过...

├ 测试数据 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]

样例没过还对了....郁闷..

贪贪！！ 那位大牛解释一下DP啊

第一次计算距离时忘记加abs WA了4个点

第二次

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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