UVa 216 - Getting in Line， 暴力与回溯
216 - Getting in Line725937.24%246372.39%
题目链接：
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=108&page=show_problem&problem=152、
题目类型： 暴力，回溯法
题目：
Computer networking requires that the computers in the network be linked.
This problem considers a ``linear" network in which the computers are chained together so that each is connected to exactly two others except for the two computers on the ends of the chain which are connected to only one other computer. A picture is shown below. Here the computers are the black dots and their locations in the network are identified by planar coordinates (relative to a coordinate system not shown in the picture).
Distances between linked computers in the network are shown in feet.
For various reasons it is desirable to minimize the length of cable used.
Your problem is to determine how the computers should be connected into such a chain to minimize the total amount of cable needed. In the installation being constructed, the cabling will run beneath the floor, so the amount of cable used to join 2 adjacent computers on the network will be equal to the distance between the computers plus 16 additional feet of cable to connect from the floor to the computers and provide some slack for ease of installation.
The picture below shows the optimal way of connecting the computers shown above, and the total length of cable required for this configuration is (4+16)+ (5+16) + (5.83+16) + (11.18+16) = 90.01 feet.
65 1955 2838 10128 62111 8443 116511 2784 99142 8188 3095 383132 7349 8672 1110
**********************************************************Network #1Cable requirement to connect (5,19) to (55,28) is 66.80 feet.Cable requirement to connect (55,28) to (28,62) is 59.42 feet.Cable requirement to connect (28,62) to (38,101) is 56.26 feet.Cable requirement to connect (38,101) to (43,116) is 31.81 feet.Cable requirement to connect (43,116) to (111,84) is 91.15 feet.Number of feet of cable required is 305.45.**********************************************************Network #2Cable requirement to connect (11,27) to (88,30) is 93.06 feet.Cable requirement to connect (88,30) to (95,38) is 26.63 feet.Cable requirement to connect (95,38) to (84,99) is 77.98 feet.Cable requirement to connect (84,99) to (142,81) is 76.73 feet.Number of feet of cable required is 274.40.**********************************************************Network #3Cable requirement to connect (132,73) to (72,111) is 87.02 feet.Cable requirement to connect (72,111) to (49,86) is 49.97 feet.Number of feet of cable required is 136.99.
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#define MAXN 200using namespace std;int n,arr[MAXN],ans[MAXN];double minSum, x[MAXN], y[MAXN];bool vis[MAXN];double dis(double x1, double y1, double x2, double y2){ return pow((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2), 0.5);}void dfs(int cur, double sum){ if(cur==n){ if(sum < minSum){ minSum = sum; memcpy(ans, arr, sizeof(arr)); } return ; } if(sum >= minSum) return; for(int i=0; i<n; ++i){ if(vis[i]) continue; vis[i] = true; arr[cur] = i; if(cur==0) dfs(cur+1, 0); else{ double t = dis(x[arr[cur]], y[arr[cur]], x[arr[cur-1]], y[arr[cur-1]]); dfs(cur+1, sum+t+16); } vis[i] = false; // 回溯后清除上次的状态，这个是重点 }}int main(){#ifdef LOCAL freopen("input.txt","r",stdin);#endif int cas=1; while(~scanf("%d", &n) && n){ for(int i=0; i<n; ++i) scanf("%lf %lf", &x[i], &y[i]); for(int i=0; i<n; ++i) arr[i] = i; minSum = 2147483646; memset(vis, 0, sizeof(vis)); dfs(0, 0); printf("**********************************************************\n"); printf("Network #%d\n", cas++); for(int i=1; i<n; ++i){ double t = dis(x[ans[i]], y[ans[i]], x[ans[i-1]], y[ans[i-1]]); printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2lf feet.\n", (int)x[ans[i-1]],(int)y[ans[i-1]],(int)x[ans[i]],(int)y[ans[i]], t+16); } printf("Number of feet of cable required is %.2f.\n", minSum); } return 0;}