Ural 1588 Jamaica[平面图最短路?]

http://acm.timus.ru/problem.aspx?space=1&num=1588

题目一点也不不像所说的那么神。。。虽然标准的O(N^2 * logN)的算法不会吧。不过O(N^3)的算法还是能过的。

给你平面上N个点(<=300)。两两连边,求生成网络的路径总长,注意在同一直线上的边长不要重复计算。

O(N^2)预处理出每两点间最短路。然后利用类似floyd的想法N^3枚举出需要处理掉的边,即诸如d[i][j] = d[i][k] + d[k][j]的边,统计所有边长的时候不要加入此种d[i][j]的值。
关键点1:用double的坏处就在这了,自带常矬卡精度。随随便便就可以构造出那种三点构成的三角形最大内角近似180度的情况用来卡这种处理方式。
即三点近似共线的情况用于卡这个式子fabs(d[i][j] - d[i][k] - d[k][j]) < eps。。一开始eps=1e-6果断被卡了,处理到1e-9才在题目给出的数据范围(10^4)下可以不被精度所影响。
“精度”啊“精度”!!!
关键点2:平常不注意cout输出流的格式自适应,用的太习惯以致于察觉不到这种最常见的小事。这你妹。我真是个蒟蒻啊。
cout输出流对于大double数如果不iomanip的话是会自动用科学计数法输出的!!!平常用cout输出二分中间结果的时候经常会看到,现在怎么想不到了呢!!!我真是太弱了。。。
所以对于哪怕题目要求最后输出四舍五入后的整数,也不要“cout<<floor(x+eps)<<endl”,而要"printf("%.0lf\n",floor(x+eps))"。。今天唯一一次想偷懒结果就悲剧了。这,人懒不得啊。。。。

少年啊,要记住,非常习惯的事物的小小细节也许是你不曾注意到的坑你的地方。世界上的事情不要想当然。无论在什么方面。

posted on 2011-08-21 01:15 BUPT-[aswmtjdsj] @ Penalty 阅读(323) 评论(0)  编辑 收藏 引用 所属分类: 计算几何Ural Solution Report教训


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年8月>
31123456
78910111213
14151617181920
21222324252627
28293031123
45678910

导航

统计

常用链接

留言簿(1)

随笔分类(150)

随笔档案(71)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜