题目分析题目要求在平面上给定nnn个点2≤n≤82 \leq n \leq 82≤n≤8将它们连成一条链线性网络使得链的总长度最小。需要注意的是每段连接电缆的长度不是两点之间的欧几里得距离而是距离16 1616英尺用于连接地板到计算机以及安装余量。输入包含多个数据集每个数据集第一行为计算机数量nnn接下来nnn行每行为一个计算机的坐标整数000到150150150之间。以n0n 0n0结束输入。输出要求对于每个数据集先输出网络编号然后按照链的顺序输出每段电缆的长度保留两位小数最后输出总电缆长度。不同数据集之间用*分隔。解题思路由于n≤8n \leq 8n≤8可以使用全排列枚举所有可能的连接顺序。对于每种排列计算相邻点之间的欧氏距离加上161616后累加取最小值即为最优方案。具体步骤预处理所有点对之间的欧几里得距离存入矩阵matrix[i][j]。生成000到n−1n-1n−1的全排列每个排列表示访问点的顺序。对每个排列计算总长度sum(matrix[perm[i]][perm[i1]])。记录总长度最小的排列并保存该排列。输出时按最优排列的顺序输出每段电缆的长度距离16 1616以及总和。时间复杂度为O(n!⋅n)O(n! \cdot n)O(n!⋅n)n≤8n \leq 8n≤8时完全可行。代码实现// Getting in Line// UVa ID: 216// Verdict: Accepted// Submission Date: 2016-04-30// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 点的结构体存储坐标structpoint{intx,y;};vectorpointnetwork;// 存储所有计算机的坐标intcases0,computers;// cases 为网络编号computers 为计算机数量doublematrix[8][8];// 存储点对之间的欧氏距离// 计算两点之间的欧氏距离doubledistances(point a,point b){returnsqrt((a.x-b.x)*(a.x-b.x)(a.y-b.y)*(a.y-b.y));}// 计算并输出当前数据集的最优布线方案voidcalculate(){// 预处理所有点对之间的距离for(inti0;icomputers;i)for(intj0;jcomputers;j)matrix[i][j]distances(network[i],network[j]);// 初始化排列为 0, 1, 2, ..., computers-1vectorintpermutation;for(inti0;icomputers;i)permutation.push_back(i);// best 用于存储最优排列minimum 存储当前找到的最小总长度vectorintbest(permutation.size());doubleminimumnumeric_limitsint::max();// 枚举所有全排列do{doublecurrentLength0.0;// 计算当前排列下相邻点之间的欧氏距离之和for(inti0;icomputers-1;i)currentLengthmatrix[permutation[i]][permutation[i1]];// 更新最优解if(currentLengthminimum){minimumcurrentLength;copy(permutation.begin(),permutation.end(),best.begin());}}while(next_permutation(permutation.begin(),permutation.end()));cases;// 网络编号递增// 输出结果cout**********************************************************endl;coutNetwork #casesendl;doublelength0.0;for(inti0;ibest.size()-1;i){coutCable requirement to connect (;coutnetwork[best[i]].x,network[best[i]].y) to (;coutnetwork[best[i1]].x,network[best[i1]].y) is ;// 每条电缆长度 欧氏距离 16doublecablematrix[best[i]][best[i1]]16.0;coutfixedsetprecision(2)cable;cout feet.endl;lengthcable;}coutNumber of feet of cable required is ;coutfixedsetprecision(2)length;cout.endl;}intmain(){cin.tie(0);cin.sync_with_stdio(false);while(cincomputers,computers){network.clear();// 读取每个计算机的坐标for(inti1;icomputers;i){point dot;cindot.xdot.y;network.push_back(dot);}calculate();}return0;}总结本题的核心是枚举全排列求解旅行商问题的朴素解法由于数据量小直接枚举即可。需要注意两点电缆长度计算公式为distance16distance 16distance16而非单纯的距离。输出格式要求严格每个网络输出前有一行*分隔且每段电缆和总长度均保留两位小数。