[cpp]
描述：水題，就不解釋了……
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
double count;
int n,step[10];
void dfs(int cur,double sum,int *flag,int (*p)[10])
{
if(cur>n)
{
if(sum<count)
{
count=sum; www.2cto.com
for(int i=1; i<=n; i++) step[i]=flag[i];
}
return;
}
else for(int i=1; i<=n; i++)
{
int j;
for( j=1; j<=n; j++)
if(flag[j]==i) break;
if(flag[j]==i) continue;
flag[cur]=i;
if(cur>=2)
{
int x=p[0][flag[cur-1]],y=p[1][flag[cur-1]];
double c=sqrt((p[0][i]-x)*(p[0][i]-x)+(p[1][i]-y)*(p[1][i]-y));
dfs(cur+1,sum+c,flag,p);
}
else dfs(cur+1,sum,flag,p);
flag[cur]=0;
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("a.txt","r",stdin);
#endif
int j(0),num[2][10],flag[10];
while(scanf("%d",&n)!=EOF)
{
if(!n) break;
memset(num,0,sizeof(num));
memset(flag,0,sizeof(flag));
printf("**********************************************************\n");
printf("Network #%d\n",++j);
count=100000;
for(int i=1; i<=n; i++)
scanf("%d%d",&num[0][i],&num[1][i]);
dfs(1,0,flag,num);
for(int i=1; i<n; i++)
{
int x1=num[0][step[i]],y1=num[1][step[i]],x2=num[0][step[i+1]],y2=num[1][step[i+1]];
printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2lf feet.\n",x1,y1,x2,y2,sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))+16);
}
printf("Number of feet of cable required is %.2lf.\n",count+(n-1)*16);
}
return 0;
}
