题目名称	6. 线型网络
输入输出	`linec.in/out`
难度等级	★★☆
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	10
题目来源	cqw 于2008-02-29加入
开放分组	全部用户
提交状态
分类标签	图论随机化 NP问题数位DP 动态规划
	分享题解

通过：165，提交：1077，通过率：15.32%
OI永别	100	0.009 s	0.25 MiB	C++
1azyReaper	100	0.010 s	0.33 MiB	C++
hahaha	100	0.010 s	0.33 MiB	C++
OI永别	100	0.010 s	0.36 MiB	C++
zjmfrank2012	100	0.016 s	0.33 MiB	C++
Steve	100	0.017 s	0.32 MiB	C++
Steve	100	0.017 s	0.32 MiB	C++
digital-T	100	0.018 s	0.32 MiB	C++
chad	100	0.018 s	0.32 MiB	C++
cstdio	100	0.018 s	0.33 MiB	C++

关于线型网络的近10条评论(全部评论)
模拟退火又被薄纱 qyd 2024-08-01 10:29 26楼
QaQ.... sxysxy 2017-04-05 09:03 25楼
为什么我的随机化一直错第5——9个点，哪位大神帮忙看一下泪寒之雪 2017-03-14 08:58 24楼
感谢liu_runda指点，终于解了心头大恨了 Hzoi_chairman 2016-11-14 08:00 23楼
用最小生成树写只过了一个点。。。随机次数50次只过了6个点，索性开到2000，终于过了。。。退役倒计时。。。 Zwoi_只会打表抄代码的蒟蒻 2016-11-08 20:20 22楼
Tabing010102 2016-11-05 21:26 21楼
最后一个点过不去……打表了…… Hzoi_Aurora 2016-11-03 17:57 20楼
随机化真是拼RP，，， Tabing010102 2016-10-13 21:39 19楼
回复 @赵日天 : 哥们，你这算法是叫状压DP，不是数位DP。核糖核酸 2016-09-27 22:15 18楼
神犇的常数比我小的不知道到哪里去了 FoolMike 2016-09-16 18:23 17楼

6. 线型网络

★★☆ 输入文件：linec.in 输出文件：linec.out 简单对比
时间限制：1 s 内存限制：256 MiB

【问题描述】

有 $N(N<=20)$ 台 PC 放在机房内，现在要求由你选定一台 PC，用共 $N-1$ 条网线从这台机器开始一台接一台地依次连接他们，最后接到哪个以及连接的顺序也是由你选定的，为了节省材料，网线都拉直。求最少需要一次性购买多长的网线。（说白了，就是找出 $N$ 的一个排列 $P_1 P_2 P_3 ..P_N$ 然后 $P_1 -> P_2 -> P_3 -> ... -> P_N$ 找出 $|P_1P_2|+|P_2P_3|+...+|P_{N-1}P_N|$ 长度的最小值）

【输入格式】

第一行 $N$，下面 $N$ 行，每行分别为机器的坐标 $(x,y)$（$x$ 为实数 $-100\le x,y\le 100$）

【输出格式】

最小的长度，保留两位小数。

【输入样例】

【输出样例】

2.83