首页 > 代码库 > UVa 216 - Getting in Line
UVa 216 - Getting in Line
题目:给你n台电脑所在的平面位置,求把他们连乘线型网络需要的最小的网线长度。
分析:搜索,枚举。
因为数据规模很小,枚举所有电脑的全排列,每一个排列对应一种连线方式。
枚举所有的连线方式,找到其中最小的,输出路径即可。
说明:开始以为是最短路或者最小生成树类似物(⊙_⊙)。
#include <iostream> #include <cstdlib> #include <cstdio> #include <cmath> using namespace std; typedef struct pnode { int x,y; }point; point P[10]; double dist(point a, point b) { return sqrt(0.0+(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))+16.0; } int link[40320][10]; int l_count; int used[10],save[10]; void dfs(int d, int n) { if (d == n) { for (int i = 0 ; i < n ; ++ i) link[l_count][i] = save[i]; l_count ++; return; } for (int i = 0 ; i < n ; ++ i) if (!used[i]) { used[i] = 1; save[d] = i; dfs(d+1, n); used[i] = 0; } } int main() { int n,t = 1; while (~scanf("%d",&n) && n) { for (int i = 0 ; i < n ; ++ i) scanf("%d%d",&P[i].x,&P[i].y); for (int i = 0 ; i < n ; ++ i) used[i] = 0; l_count = 0; dfs(0, n); double min = 3000.0; int spa = 0; for (int i = 0 ; i < l_count ; ++ i) { double sum = 0.0; for (int j = 1 ; j < n ; ++ j) sum += dist(P[link[i][j-1]], P[link[i][j]]); if (sum < min) { min = sum; spa = i; } } printf("**********************************************************\n"); printf("Network #%d\n",t ++); for (int j = 1 ; j < n ; ++ j) printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2lf feet.\n", P[link[spa][j-1]].x,P[link[spa][j-1]].y,P[link[spa][j]].x,P[link[spa][j]].y, dist(P[link[spa][j-1]], P[link[spa][j]])); printf("Number of feet of cable required is %.2lf.\n",min); } return 0; }
UVa 216 - Getting in Line
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。