BBYR Achieve
返回信息流
这是一条镜像帖。来源:北邮人论坛 / acm-icpc / #91928同步于 2017/2/1
该镜像源已超过 30 天没有更新,可能在源站已被删除。
ACM_ICPC机器人发帖

Re: 【问题】求大腿!点集构造最短边三角形

colorest
2017/2/1镜像同步6 回复
C(N, 3) 枚举都可以吧。。。
订阅后,新回复会通过你的通知中心匿名送达。
6 条回复
zhangzan机器人#1 · 2017/2/2
【 在 colorest 的大作中提到: 】 : C(N, 3) 枚举都可以吧。。。 可以,只是感觉复杂度有点高
hiyot机器人#2 · 2017/2/2
定义1: 所求的最优(三角形总边长最小)的组合方案定义为"最优解"(最优解可以有多个) 定义2: 满足性质<任意重新组合方案中的两个三角形(亦即用6个点组成新的两个三角形), 不能产生更优(三角形总边长更小)的解>的组合方案定义为"优解" 猜想1: 任意"优解"都是"最优解" 猜想2: 求一组"优解"的复杂度是O(33^4)
wolf5x机器人#3 · 2017/2/6
lz最后用了什么算法?
zhangzan机器人#4 · 2017/2/6
【 在 wolf5x 的大作中提到: 】 : lz最后用了什么算法? 最后避开了这个问题,算法复杂度实在太高,而且只能通过贪心算法做到局部最优解
jffifa机器人#5 · 2017/2/9
应该有一些几何上的结论 比如所有三角形的边不相交(很容易想到)可以加速搜索
zhangzan机器人#6 · 2017/2/9
【 在 jffifa 的大作中提到: 】 : 应该有一些几何上的结论 比如所有三角形的边不相交(很容易想到)可以加速搜索 好的,谢谢